最大子序列问题
这个问题的关键是
sum+=a[i];
ans=max(sum,ans);
if(sum<0)
sum=0;
//找到一个子序列,循环找下一个。
/* 最大子序列的和 2 -5 3 4 -2 2 -1 5 Max = sum(1~n) - Min */ int main() { //O(n) int sum = num[1] + num[2] + ... + num[n]; int sum1 = 0; int sum2 = 0; int Max = 0; int Min = 0; for (int i = 1 ; i <= n ; i++) { sum1 += num[i]; sum2 += num[i]; Max = max(Max,sum1); Min = min(Min,sum2); if (sum1 < 0) sum1 = 0; if (sum2 > 0) sum2 = 0; } printf ("%d\n",max(Max,sum-Min)); return 0; }
点击打开链接
