一开始有了个n*n的算法，就是把原来的数组*2，由环形的展开成数组。然后调用n次最大子段和的方法。超时。
后来看到个O(n)的算法，就是如果不跨越末尾，就是最大字段和；如果跨越末尾，就是sum-（最小子段和）http://blog.csdn.net/hackbuteer1/article/details/6694193
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 |
int
maxConsSum2(const
vector<int> &arr) { if
(arr.size() == 0) return
0; int
dp = 0; int
max1 = 0; for
(int
i = 0; i < arr.size(); i++) { if
(dp < 0) dp = 0; dp += arr[i]; if
(dp > max1) max1 = dp; } dp = arr[0]; int
min = arr[0]; int
sum = arr[0]; for
(int
i = 1; i < arr.size(); i++) { if
(dp > 0) { dp = arr[i]; } else
{ dp += arr[i]; } if
(dp < min) min = dp; sum += arr[i]; } int
max2 = sum - min; if
(max1 > max2) return
max1; else
return
max2;} |
原文：http://www.cnblogs.com/lautsie/p/3523226.html