扣初级算法-32-动态规划-最大子序和

2021/12/6 1:17:04

本文主要是介绍扣初级算法-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;
	}


}



这篇关于扣初级算法-32-动态规划-最大子序和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程