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

题解一： 动态规划
题解思路：使用dp数组表示子问题累加和， ans表示当前数组累加和最大值
图示：

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N)
实现如下：

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int len = arr.size()-1;
        int dp[len+1]; 
        memset(dp, 0, sizeof(dp));
        dp[0] = arr[0];
        int ans = arr[0];
        for(int i = 1;i<=len; i++){
            dp[i] = dp[i-1]+arr[i] > arr[i] ? dp[i-1]+arr[i] : arr[i];
            ans = max(dp[i],ans);  //更新最大累加和
        }
        return ans;

    };
};

题解二：优化动态规划空间复杂度
题解思路： 可以使用一个cur_sum表示当前累加和，如果在arr[i]处，cur_sum < 0, cur_sum = arr[i]; ans依然保存当前最大累加和。
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)
实现如下：

class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        int ans = arr[0];
        int cur_max = arr[0];
        for(int i = 1;i<arr.size();i++){
            cur_max = cur_max + arr[i] > arr[i] ? cur_max+arr[i] : arr[i]; // 更新当前累积和
            ans = max(cur_max , ans);  // 更新最大累积和
        }
        return ans;
    }
};

题解三：二分法
题解思路：将数组分为两部分，最大和分为三种情况。
图示：

复杂度分析：
时间复杂度：O(NlogN)
空间复杂度：O(logN) : 递归栈深度

实现如下：

class Solution {
public:
      int merge_max(int left,int mid,int right,vector<int>& arr){
        int left_sum = 0;
        int leftmax = INT_MIN;
        // 从mid开始，向左计算累加和
        for(int i = mid;i>=left;i--){
            left_sum += arr[i];
            leftmax = max(left_sum,leftmax);
        }
        int right_sum = 0;
        int rightmax = INT_MIN;
        // 从mid开始，向左计算累加和
        for(int i = mid+1;i<=right;i++){
            right_sum += arr[i];
            rightmax = max(right_sum, rightmax);
        }
        return rightmax+leftmax;  // 左右最大累加和相加
    }
    int search_max(int left,int right,vector<int>& arr){
        if(left==right) return arr[left];
            int mid = (left+right)>>1;
            int left_sum = search_max(left, mid, arr);  //求左边最大值
            int right_sum = search_max(mid+1,right,arr);  //求右边累加最大值
            int merge_sum = merge_max(left,mid,right,arr);  //合并累加最大值
            return max(max(left_sum,right_sum),merge_sum);
    }
    int maxsumofSubarray(vector<int>& arr) {
        return search_max(0, arr.size()-1, arr);
    }
};