动态规划（一）最大子序和

vlambda
2021-09-13

动态规划（一）最大子序和

最大子序和

原题链接：https://leetcode-cn.com/problems/maximum-subarray/

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：连续子数组 [4,-1,2,1] 的和最‍‍大，为 6 。

这个一道可以使用动态规则比较典型的题目。

由于是连续子数组，故在遍历数组时，之前数组加起来的和大于0，之后加上任和大于0的数，都将使值增大。遍历到数组的某一位（大于0）时，其最大值就是前一个最大值加上本身或者就是本身。

例题中：

状态转移方程为 f(i) = Math.max(f(i-1)+nums[i],nums[i])

f(1) = Math.max(f(0) + 1,1) = -1

f(2) = Math.max(f(1) - 3, -3) = -2

f(3) = Math.max(f(2) + 4, 4) = 4

f(4) = Math.max(f(3) -1, -1) = 3

f(5) = Math.max(f(4) + 2, 2) = 5

f(6) = Math.max(f(5)+ 1, 1) = 6

f(7) = Math.max(f(6) - 5, -5) = 1

f(8)= Math.max(f(7)+ 4, 4) = 5

其状态转移方程是 f{i) = Math.max(f(i+1)+nums[i] , nums[i])

题目代码

有了状态转移方程，动态规划的题目就比较好写，代码如下：

 public int maxSubArray(int[] nums) { if(nums == null || nums.length == 0){ return 0; }
 // 假设前一位的最大值为 0 int pre = 0; // 假设整个子序列最大值是数组的第一位 int max = nums[0]; // 假设当前最大值是 0 int cur = 0; // 遍历数组 for (int num : nums) { // 前一位的最大值是 cur = Math.max(pre+num,num); // 保存遍历过程中的最大值 max = Math.max(max,cur); // 下一个的最大值为当前的值，继续遍历 pre = cur; } return max;    }