最近开始练习DP的算法问题。Maximum Subarray 问题属于比较经典的入门级动归问题了,仔细研读了一下Wikipedia上面的Kadane’s Algorithm,想了一会儿,明白了算法的原理。
HackerRank上面的题目是这样的:
给出一个数组,其中的数有正有负,求最大连续子序列的和,以及最大非连续子序列的和。其中连续子序列的和的求解即可使用Kadane’s Algorithm来解决。
非连续子序列的和,我们的第一反应是,遍历数组,累加所有的非负数,最后的和即是结果。但是这样的算法木有考虑到数组中全是负数的情况。如果数组中所有的数都为负的话,其实最大非连续子序列的和也就等于Kadane’s Algorithm所计算出来的最大连续子序列的和:也就是数组中最大的数。

void calc(vector<int>& vi) {
    int ret;
    int pass = ret = vi[0];
    for (int i=1; i<vi.size(); i++) {
        int x = vi[i];
        pass = max(x, pass+x);
        ret = max(pass, ret);
    }
    if (ret < 0) {
        cout << ret << " " << ret << endl;
    }
    else {
        int sum = 0;
        for (vector<int>::iterator ite = vi.begin(); ite != vi.end(); ite++) {
            if (*ite > 0) sum += *ite;
        }
        cout << ret << " " << sum << endl;
    }
}