建行官方网站 - 百度wordpress 手机页面

题目：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

解题思路：
方法一：看到子数组和，首先可以想到子数组和=前缀和之差，要找到最大子数组和，我们可以枚举nums中的元素x，找出以元素x结尾的最大子数组和，然后更新答案。

要寻找以元素x结尾的最大子数组和，我们只需要知道x元素之前的最小子数组和。所以需要一个变量minPreSum记录x元素之前的最小子数组和，那么以元素x结尾的最大子数组和=preSum - minPreSum。

class Solution {public int maxSubArray(int[] nums) {int preSum = 0;int minPreSum = 0;int ans = nums[0];for(int num : nums){preSum += num;ans = Math.max(ans, preSum - minPreSum);minPreSum = Math.min(minPreSum, preSum);}return ans;}
}

方法二：动态规划。要知道以x结尾的最大子数组和，我们可以通过以x-1结尾的最大子数组和推导出来。状态转移方程为dp[i] = max(dp[i-1] + nums[i], nums[i])，dp[i]表示以i结尾的最大子数组和，在枚举i的过程中更新答案。

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

优化：
因为在计算dp[i]的过程中只会用到dp[i-1]，所以我们可以用一个变量来代替。

class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int x = 0;for(int num : nums){x = Math.max(x + num, num);ans = Math.max(x, ans);}return ans;}
}