[数据结构与算法]扣初级算法-32-动态规划-最大子序和

学习目标：

本次学习目标为 力扣初级算法-动态规划，其中主要的LC如下：

• 最大子序和

学习内容：

1. 最大子序和 -----（[链接](https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/）
   给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
   子数组 是数组中的一个连续部分。

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

示例 2：
输入：nums = [1]
输出：1

解题思路：

• 解法一： 通用
• 解题思路：
  • 动态规划四要个步骤
  • 1.确定状态
  • 2.找到转移公式
  • 3.确定初始条件以及边界问题
  • 4.计算结果
  • 解法一：通用
  • 动态规划
    • 四个步骤
    • 1.确定状态
    • 2.找到转移公式
    • 3.确定初始化条件以及边界条件
    • 4.计算结果
    • 具体如下：
      • 1.定义 dp[i] 表示数组中前i+1个元素构成的连续子数组的最大和。
      • 2.如果计算前 i+1 个元素构成的子数组的最大和，也就是计算 都dp[i]。
      • 此处需要判断 dp[i-1] 是大于 0 还是 小于 0 ，此处可能会疑惑为什么是跟 0 做比较。— 因为当前数，只要相加的数是小于 0 的，那么其对应的值肯定是降低的。
      • 如果dp[i-1]大于0，就继续累加，dp[i]=dp[i-1]+num[i]
      • 如果dp[i-1]小于0，我们直接把前面的舍弃，也就是说重新开始计算，否则会越加越小的，直接让dp[i]=num[i]
      • 故可得出 转移公式是 dp[i]=num[i]+max(dp[i-1],0);
      • 3.边界条件问题：当i等于0的时候，也就是前1个元素，他能构成的最大和也就是他自己，所以
      • dp[0]=num[0];
  • 代码实现：

public class MaxSubArray {

	/**
	 * 动态规划
	 * 四个步骤
	 * 1.确定状态
	 * 2.找到转移公式
	 * 3.确定初始化条件以及边界条件
	 * 4.计算结果
	 *
	 * 1.定义 dp[i] 表示数组中前i+1个元素构成的连续子数组的最大和。
	 * 2.如果计算前 i+1 个元素构成的子数组的最大和，也就是计算 都dp[i]。
	 * 此处需要判断 dp[i-1] 是大于 0  还是 小于 0 ，此处可能会疑惑为什么是跟 0 做比较。--- 因为当前数，只要相加的数是小于 0 的，那么其对应的值肯定是降低的。
	 * 如果dp[i-1]大于0，就继续累加，dp[i]=dp[i-1]+num[i]
	 * 如果dp[i-1]小于0，我们直接把前面的舍弃，也就是说重新开始计算，否则会越加越小的，直接让dp[i]=num[i]
	 * 故可得出 转移公式是 dp[i]=num[i]+max(dp[i-1],0);
	 * 3.边界条件问题：当i等于0的时候，也就是前1个元素，他能构成的最大和也就是他自己，所以
	 * dp[0]=num[0];
	 */
	public int maxSubArray(int[] nums) {
		int length = nums.length;
		int[] dp = new int[length];
		// 边界问题
		dp[0] = nums[0];
		int current = dp[0];
		int max = current;
		for (int i = 1; i < length; i++) {
			current = Math.max(dp[i -1], 0) + nums[i];
			max  = Math.max(current, max);
		}

		return max;
	}


}