8-7

xiaoxiao2021-02-28  106

最大子序列问题

这个问题的关键是

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; }

点击打开链接

转载请注明原文地址: https://www.6miu.com/read-78191.html

最新回复(0)