- C/C++ code
#include <stdio.h> #include <conio.h> #define N 6 main() { int i; int a[N]={-2,11,-4,13,-5,-2}; printf("the old older is:n"); for(i=0;i<N;i++) printf("%d ",a[i]); printf("n"); i=MaxSubsequenceSum4(a,N); printf("the max is %dn",i); printf("n"); getch(); } int MaxSubsequenceSum4(const int a[],int n) { int ThisSum,MaxSum,j; ThisSum=MaxSum=0; for(j=0;j<n;j++) { ThisSum+=a[j]; if(ThisSum>MaxSum) MaxSum=ThisSum; else if(ThisSum<0) MaxSum=0; } return MaxSum; }
------解决方案--------------------
利用动态规划的思想 添加一个数组 记录前n项的和 最大的子串和 是两个数组的差的最大值