LeetCode 53.最小子数组和

本文主要是介绍LeetCode 53.最小子数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode-cn.com/problems/maximum-subarray/
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

思路：
定义一个子问题，将问题拆解，并使各个子问题之间有联系。
找出具有最大和的连续子数组 ====> 以数组每一项为结尾的连续子数组的最大和是多少
状态转移方程为：
dp[i] = dp[i - 1] + nums[i]
如果dp[i - 1]是负数，则最大和为nums[i]
所以 dp[i] = max(dp[i - 1] + nums[i], nums[i])

var maxSubArray = function(nums) {let dp = new Array(nums.length).fill(0);let sum = nums[0];dp[0] = nums[0];for (let i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);sum = Math.max(sum, dp[i]);}return sum;
};

状态压缩

var maxSubArray = function(nums) {var pre = 0var max = nums[0]for(let i = 0; i < nums.length; i++) {pre = Math.max(nums[i], nums[i] + pre)max = Math.max(max, pre)}return max
};

这篇关于LeetCode 53.最小子数组和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---