LeetCode_动态规划_简单_53.最大子数组和

缺乏、安全感 2023-10-06 18:58 38阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）
 *  4.扩展

## 1.题目 ##

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

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

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

**示例 3：**  
输入：nums = \[0\]  
输出：0

**示例 4：**  
输入：nums = \[-1\]  
输出：-1

**示例 5：**  
输入：nums = \[-100000\]  
输出：-100000

**提示：**  
1 <= nums.length <= 3 \* 104  
\-105 <= nums\[i\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-subarray

## 2.思路 ##

（1）暴力穷举法  
使用两层 for 循环穷举出所有的情况，在此过程中保存最大的子序和即可。不过该方法的缺点在于时间复杂度较高！

（2）动态规划  
根据题意，可定义 dp\[j\] 如下：  
![在这里插入图片描述][d6b529b06d18430e842653407a936caa.png]  
所以当 dp\[j - 1\] > 0时，dp\[j\] = dp\[j - 1\] + nums\[j\]，否则 dp\[j\] = nums\[j\]，由此可得状态转移方程为 **dp\[j\] = max\{dp\[j - 1\] + nums\[j\], nums\[j\]\}，0 ≤ j ≤ nums.length - 1**，据此便可以设计出求最大子序和的动态规划算法。  
不过需要注意的是在编写代码时并不需要定义 dp 数组，而只需定义初始值为 0 整数 dp 即可，**由于本题只要求遍历数组 nums 过程中的子序和最大值，即用 sum 动态保存当前所求的最大值即可**，当遍历结束时，sum 的值即为最大子序和，因此不需要 dp 数组来保存所有的中间结果。

相关题目：  
[LeetCode\_动态规划\_中等\_918.环形子数组的最大和][LeetCode_918.]  
[LeetCode\_动态规划\_中等\_1749.任意子数组和的绝对值的最大值][LeetCode_1749.]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int length = nums.length;
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < length; i++) {
        
                int tmpRes = 0;
                for (int j = i; j < length; j++) {
        
                    tmpRes += nums[j];
                    res = Math.max(tmpRes, res);
                }
            }
            return res;
        }
    }

//思路2————动态规划
    class Solution {
        
        public int maxSubArray(int[] nums) {
        
            // dp[i] = j 表示以 nums[i] 结尾的子数组最大和为 j
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            // res 记录数组 nums 的连续子数组的最大和
            int res = dp[0];
            for (int i = 1; i < nums.length; i++) {
        
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }
    
    //降低空间复杂度的写法
    class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int res = Integer.MIN_VALUE;
            int dp = 0;
            for (int i = 0; i < nums.length; i++) {
        
                dp = Math.max(dp + nums[i], nums[i]);
                res = Math.max(res, dp);   
            }
            return res;
        }   
    }

## 4.扩展 ##

在计算最大子数组和之前，我们可以选择将数组 nums 中的某一个元素修改为 x，也可以选择不修改，然后再求最大子数组和：

class Solution {
        
        public static int maxSubArray(int[] nums, int x) {
        
            int n = nums.length;
            // dp[i][j] 表示以 nums[i] 结尾并经过 j 次修改的子数组的最大和
            int[][] dp = new int[n][2];
            //保存最终结果
            int res = nums[0];
            dp[0][0] = nums[0];
            dp[0][1] = Math.max(nums[0], x);
            for (int i = 1; i < n; i++) {
        
                dp[i][0] = Math.max(dp[i - 1][0] + nums[i], nums[i]);
                dp[i][1] = Math.max(Math.max(dp[i - 1][0] + x, dp[i - 1][1] + nums[i]), x);
                res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
            }
            return res;
        }
    }

[d6b529b06d18430e842653407a936caa.png]: https://img-blog.csdnimg.cn/d6b529b06d18430e842653407a936caa.png
[LeetCode_918.]: https://blog.csdn.net/weixin_43004044/article/details/131206398
[LeetCode_1749.]: https://xgqngu.blog.csdn.net/article/details/132160261