LeetCode-53. 最大子数组和

女爷i 2024-03-24 08:28 78阅读 0赞

#### 目录 ####

*   *  动态规划

题目来源  
[53. 最大子数组和][53.]

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]：包括下标i（以nums\[i\]为结尾）的最大连续子序列和为dp\[i\]。

int[] dp = new int[nums.length];

*  2.确定递推公式

dp\[i\]只有两个方向可以推出来：  
dp\[i - 1\] + nums\[i\]，即：nums\[i\]加入当前连续子序列和  
nums\[i\]，即：从头开始计算当前连续子序列和  
一定是取最大的，所以dp\[i\] = Math.max(dp\[i - 1\] + nums\[i\], nums\[i\]);

dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

*  3.dp数组如何初始化

从递推公式可以看出来dp\[i\]是依赖于dp\[i - 1\]的状态，dp\[0\]就是递推公式的基础。  
根据dp\[i\]的定义，很明显dp\[0\]应为nums\[0\]即dp\[0\] = nums\[0\]。

dp[0] = nums[0];

*  4.确定遍历顺序

递推公式中dp\[i\]依赖于dp\[i - 1\]的状态，需要从前向后遍历。  
最大不一定是最后一个位置，所以我们要定义一个result求出最大的值

for(int i = 1;i<nums.length;i++){
        
                dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
                result = dp[i] > result ? dp[i] : result;
            }

*  5.举例推导dp数组

以示例一为例，输入：nums = \[-2,1,-3,4,-1,2,1,-5,4\]，对应的dp状态如下：  
![在这里插入图片描述][2bbe93036560432f94738b37009b6b73.png]  
代码实现

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int result = nums[0];
            for(int i = 1;i<nums.length;i++){
        
                dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
                result = dp[i] > result ? dp[i] : result;
            }
            return result;
        }
    }

![在这里插入图片描述][81760584233d4933ab066f9c8782d953.png]

[53.]: https://leetcode.cn/problems/maximum-subarray/
[2bbe93036560432f94738b37009b6b73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3cebe577e440412aa91dbe12197f4024.png
[81760584233d4933ab066f9c8782d953.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9a280590ad3948df977ee6433dbae195.png