题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

题解

使用动态规划的思想，用dp[i]表示以第 i 个数字结尾的子数组的最大和。

状态转移方程：

时间复杂度为，空间复杂度为。（空间复杂度可以优化，即用变量代替数组）

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        
        // dp[i] = max(dp[i-1]+dp[i], dp[i])
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}