给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

分析

• 动态规划

解法

• 记录每个位置的连续子数组最大和，计算每个位置时考虑是否加上上一位的最大和连续数组

• 时间复杂度O(\(n\))，n为数组长度

• 空间复杂度O(\(1\))

class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化当前位置连续子数组最大和
        int pre = 0;
        // 初始化最终结果
        int max = nums[0];
        // 遍历数组
        for (int x : nums) {
            // 计算当前位置连续子数组最大和
            pre = Math.max(pre + x, x);
            // 更新最终结果
            max = Math.max(max, pre);
        }
        return max;
    }
}

//class Test{
//    public static void main(String[] args) {
//        Solution test = new Solution();
//        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
//        System.out.println(test.maxSubArray(nums));
//    }
//}