一开始有了个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;
} |