C++题解 | #子数组的最大累加和问题#

分治法求子数组最大累加和。
从第二个位置元素开始，依次求**包含该位置元素在内**的最大子数组累计和（即该位置元素与前一位置元素之和，与该位置元素相比，哪个更大。若前者大于后者，则将该位置元素替换为该位置元素与前一位置元素之和），之后遍历数组，查询最大值即可。

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>&amp; arr) {
        for (int i = 1; i &lt; arr.size(); i++) {
            //arr[i] = max(arr[i], arr[i - 1] + arr[i]);
            if (arr[i] &lt; arr[i - 1] + arr[i])
                arr[i] = arr[i - 1] + arr[i];
        }
        int t = INT_MIN;
        for (int i = 0; i &lt; arr.size(); i++) {
            //t = max(t, arr[i]);
            if (arr[i] &gt; t)
                t = arr[i];
        }
        return t;
    }
};