最大子序和

古城微笑少年丶 2022-12-05 10:13 178阅读 0赞

# 最大子序和 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/maximum-subarray/

## 2、题目要求 ##

> **题目描述**

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

> **示例:**

输入: [-2,1,-3,4,-1,2,1,-5,4]
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

> **进阶:**

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

## 3、代码思路 ##

动态规划

1.  还是反问一句：为什么要使用动态规划？我们求每个以 `nums[i]` 结尾的最大子序和，然后选出其中的最大值，不就好了吗？
2.  我们定义 `dp[i]` 的含义为：以 `nums[i]` 结尾的最大子序和，对于每个 `nums[i]`，我们有两种选择：自成一派或者加入集体，状态转移方程为：`dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);`，
3.  状态转移方程的其含义为：当以 `nums[i]` 结尾时，尝试着加上 `dp[i-1]`(即以 `nums[i-1]` 结尾的最大子序和)，如果该加和比 `nums[i]` 还小，则 `nums[i]` 自成一派，否则 `nums[i]` 表示打不过他们我就加入他们

## 4、代码实现 ##

代码

class Solution {
        
        public int maxSubArray(int[] nums) {
        
    
            int[] dp = new int[nums.length];
            // 当数组只有一个元素时，最大子序和就是该元素本身
            dp[0] = nums[0];
            // 默认最大子序和为 nums[0]
            int maxSum = nums[0];
    
            // 以数组中每个元素结尾，求其最大子序和
            for (int i = 1; i < nums.length; i++) {
        
                // 打不过他们我才加入他们
                dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
                // 更新数组的最大子序和
                maxSum = Math.max(dp[i], maxSum);
            }
    
            return maxSum;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关最大子序和

最大子序和 1、参考资料 https://leetcode-cn.com/problems/maximum-subarray/ 2、题目要求 > 题目描述

古城微笑少年丶/ 2022年12月05日 10:13/ 0 赞/ 179 阅读

相关 53. 最大子序和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

短命女/ 2022年10月22日 08:00/ 0 赞/ 183 阅读

相关 53.最大子序和

题目描述：给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例：输入：nums = [-2,1,-

怼烎@/ 2022年08月28日 12:52/ 0 赞/ 156 阅读

相关最大子序和

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5

妖狐艹你老母/ 2022年04月16日 02:12/ 0 赞/ 202 阅读

相关最大子序和

题目描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2

灰太狼/ 2022年02月26日 04:52/ 0 赞/ 225 阅读

相关最大子序和——最大子矩阵

[LeetCode-最大子序和][LeetCode-] 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:

清疚/ 2022年02月20日 05:52/ 0 赞/ 304 阅读

相关最大子序和

1.暴力解法 O(n^3) class Solution { public: int FindGreatestSumOfSubArray(v

快来打我*/ 2022年02月05日 12:51/ 0 赞/ 231 阅读

相关最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4

川长思鸟来/ 2022年01月20日 04:09/ 0 赞/ 245 阅读

相关 53. 最大子序和

[53. 最大子序和][53.] 题目描述给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:

缺乏、安全感/ 2021年11月02日 00:08/ 0 赞/ 287 阅读

相关 LeetCode：最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4

水深无声/ 2021年11月01日 03:08/ 0 赞/ 335 阅读