一、题目

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

点击查看原题
难度级别：简单

二、思路

1）动态规划

可以将问题抽象出来，dp[i]表示以i位置数字结尾的连续子数组最大和的值，那么dp[i+1]的值只依赖于dp[i]，其中：

若dp[i]<0，则dp[i+1]=nums[i+1] 若dp[i]>0，则dp[i+1]=nums[i+1]+dp[i]

记录dp数组中最大的值，就为本题答案
由于后一个状态只依赖于前一个状态，可以将其空间复杂度优化为常数，使用preSum代表dp[i]即可

三、代码

1）动态规划

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

时间复杂度为O(n)，空间复杂度为O(1)