求一个数组中连续子数组的最大和

/****************************************************** *@time 2016/08/13 23:35 *@Place DHU.5005 *@decription 求一个数组中连续子数组的最大和 *@思路 dp **********************************************************/ #include<cstdio> #include<algorithm> #include<stack> using namespace std; /*********************************************************** *@函数名 greatest_Sum_Of_Subarray *@parameter int * ori_Nums 原始数组 *@parameter int length 数组大小 *@返回值 int* dp数组 *@description 动态规划得到每一步的最大值 **************************************************************/ int* greatest_Sum_Of_Subarray(int * ori_Nums,int length); /************************************************************ *@函数名 print_Subarray *@parameter int *dp dp数组 *@parameter int *ori_Nums 原始数组 *@parameter int length 数组大小 *@description 打印拥有最大和连续子数组 **************************************************************/ void print_Subarray(int *dp,int *ori_Nums,int length); int* greatest_Sum_Of_Subarray(int * ori_Nums,int length) { if(ori_Nums==NULL||length<=0) return NULL; int *dp=(int*)malloc(sizeof(int)*length); for(int i=0;i<length;i++) { if(i==0||dp[i-1]<0) { dp[i]=ori_Nums[i]; } else { dp[i]=dp[i-1]+ori_Nums[i]; } } return dp; } void print_Subarray(int *dp,int *ori_Nums,int length) { int greatest_Sum=-1; int index=0; stack<int> subarray; for(int i=0;i<length;i++) { if(greatest_Sum<dp[i]) { greatest_Sum=dp[i]; index=i; } } while(greatest_Sum) { subarray.push(index); greatest_Sum-=ori_Nums[index--]; } while(!subarray.empty()) { printf("%d ",ori_Nums[subarray.top()]); subarray.pop(); } } int main() { int ori_Nums[]={-1,-2,3,10,-4,7,2,-5}; int* dp=greatest_Sum_Of_Subarray(ori_Nums,8); print_Subarray(dp,ori_Nums,8); }