53. 最大子序和 + 动态规划 + 线段树

53. 最大子序和

LeetCode_53

题目描述

方法一：动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int sums = 0;
        int maxSum = -0x3f3f3f3f;
        for(int i=0; i<len; i++){
            sums += nums[i];
            maxSum = Math.max(sums, maxSum);
            if(sums <= 0){
                sums = 0;
            }
        }
        return maxSum;
    }
}

方法二：线段树 + 分治法