[itint5]环形最大连续子段和

http://www.itint5.com/oj/#9

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

  

[itint5]环形最大连续子段和

上一篇:Cake


下一篇:Introduction of Open CASCADE Foundation Classes