子数组的最大累加和

分治

动态规划
其实题目可以用动态规划做，很简单的动态规划题目，而且也是最优解
先看代码:

public int maxsumofSubarray (int[] arr) {

        int n = arr.length;
        if(n == 1)
            return arr[0];
        int max = 0;

        for(int i = 1; i < n; i++){
            arr[i] = Math.max(arr[i],arr[i]+arr[i-1]);
            max = Math.max(max,arr[i]);
        }

        return max;
    }

图解：

优化，不修改原数组的方法

public int maxSubArray(int[] nums) {
        int ans = nums[0],sum = Integer.MIN_VALUE;
        for(int num: nums){
            if(sum >= 0){
                sum += num;
            }else{
                sum = num;
            }
            ans = Math.max(ans,sum);
        }
        return ans;
    }