LeetCode第53题最大子数组和

2023年 10月 13日 61.4k 0

继续打卡算法题,今天学习的是LeetCode第53题最大子数组和,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

本题可以使用最笨的办法,把所有连续组合求出来,最后将计算得到最大和的组合。但是可以借助一些技巧,避免保存所有的组合,我们其实可以只要存一个最大的组合值就可以,每求一个组合就和最大值比较,如果当前组合大于最大值,就更新最大组合值。

其中一个比较好的解法思路是:

每次以某个元素为组合的最后一个元素,计算当前组合的和,如果大于之前最大的组合和,那么更新最大的组合和。

[-2,1,-3,4,-1,2,1,-5,4]为例,

1、先求-2结尾的组合,最大组合和是-2

2、求1结尾的组合,最大组合和是1

3、求-3结尾的组合,最大组合和是1

....以此类推

本题解题技巧

1、每得到一个组合,就更新最大组合和,不用等所有组合求出来后再计算最大组合和

2、本题以每个元素结尾的组合,组合最大值要么是它本身,要么是之前的最大值加上它本身

3、其实这就是动态规划思想。动态规划就是解决最值问题的。

编码解决

class Solution {
public int maxSubArray(int[] nums) {

int max = nums[0];
int pre = nums[0];
for(int i=1; i

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论