一、前言
最近在力扣上刷有关动态规划的题目，正好遇到了以前写博客时的一道之前运用暴力求解的题目，现在用动态规划来对他进行一下优化
暴力求解方法对应文章传送门
求整数组中最大子数组的和
二、题目描述
LeetCode53. 最大子数组的和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
三、动态规划
既然要使用动态规划，还是一样的动态规划五部曲来解题
1️⃣确定dp数组含义
此处dp[i]的含义表示前i+1个元素（从第一个元素到nums[i]元素）的连续数组的和的最大值
2️⃣确定递推公式
当遇到的元素nums[i]之前的连续数组和的最大值dp[i-1]为负数时，则不要将现在的这个数加到dp[i-1]上，因为不知道现在的这个数nums[i]是正还是负，如果盲目加上，只会无法判断其最大子数组的和，故 dp[i-1] < 0时，dp[i] = nums[i]
而当dp[i-1]大于0时，对于i位置上的元素来说，如果num[i]为正，那么这个和就更大，如果为负，如果取num[i]的值，一定没用加上一共大于0的dp[i-1]来的大，所以dp[i-1] > 0时，dp[i] = dp[i-1] + nums[i]
3️⃣确定dp数组初始值
由于计算和，所以我们设dp数组内第一个值就是存放数据的数组内第一个值，dp[0] = nums[0]
4️⃣确定循环
这里循环很简单，就是在数组长度内执行操作即可
5️⃣确定返回值
由于此处下标值i是在循环外定义的，所以要用一个变量去接收最后的值并返回，此处我们就设变量为result，并初始化值为dp[0]，判断result和dp[i]的值，谁更大就返回谁，即result = Math.max(result,dp[i])
四、代码实现
class Solution { public int maxSubArray(int[] nums) { //定义dp数组并初始化 int n = nums.length; int[] dp = new int [n]; dp[0] = nums[0]; //定义返回值并初始化 int result = dp[0]; //利用动态规划求子数组最大值 for(int i = 1; i < nums.length; i++){ if(dp[i-1] < 0){ dp[i] = nums[i]; } else{ dp[i] = dp[i-1] + nums[i]; } //求出最大的子数组和 result = Math.max(result,dp[i]); } //返回结果 return result; } }
五、测试代码
六、结语
本文是另一道经典的动态规划题目，在看了题解以后发现还有空间优化的思路，如果有别的思路欢迎评论交流
