最大相连子序列和的 O(n^2) 算法

maxSum2.cpp

/**
 * @param a
 * @return maxsum
 * @brief 最大相连子序列和的 O(n^2) 算法
 */
int maxSubSum2(const vector<int> &a) {
    int maxSum = 0;

    for (int i = 0; i < a.size(); ++i) {
        int thisSum = 0;
        for (int j = i; j < a.size(); ++j) {
            thisSum += a[j];

            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    }

    return maxSum;
}