Leetcode | Kadane Algo | 53. 918.

9月前作者：amytheace 分类：Toy博客阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了Leetcode | Kadane Algo | 53. 918.。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

53. Maximum Subarray

如果cur_sum大于零，可以晋级到下一个元素，因为正数只会让之后的和更大。如果cursum小于零，那就把他reset成0，让下一个元素从头开始。在此过程中一直记录global max

918. Maximum Sum Circular Subarray

两种求和方式：

按照正常的区间，不circular，就是53的思路即可。可以得到一个正常区间内的max。

还有一个不正常的区间，circular，也会有一个max。

这两个max里面选最大的就好。

第二个不正常区间的circular怎么求呢？可以在算第一种max的时候同时找到正常区间内的minsum。求一个total然后total减正常区间的minsum就是不正常区间的maxsum。

注意一个全是负数的edge case。全是负数的时候total减minsum会是0，大于最大的那个负数。

108. Convert Sorted Array to Binary Search Tree

复习一下initialzie vector的方法文章来源地址https://www.toymoban.com/news/detail-621563.html

vector<int> left(nums.begin(), nums.begin() + idx);

到了这里，关于Leetcode | Kadane Algo | 53. 918.的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

LeetCode 918. Maximum Sum Circular Subarray【数组,动态规划】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，

2024年02月15日
浏览(50)
leetcode做题笔记53

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。时间复杂度O(n)，空间复杂度O(1) 本题要求最大子数组和，可考虑先求出每个元素的前缀和，再判断是否前缀和加现元素是否

2024年02月14日
浏览(57)
【LeetCode】53. 最大子数组和

这道题的状态设计和状态转移和 300. 最长递增子序列类似。但是这里要求的是连续子数组，和子序列不同。状态定义首先定义 dp[i] ：以 nums[i] 结尾的具有最大和的连续子数组。状态转移方程根据状态的定义，dp[i] 一定包含 nums[i] 。这里我们假设 nums[i] 0 ，则一定有 dp[

2024年02月02日
浏览(35)
leetcode 53. 最大子数组和

要求找最大和的连续子数组，我的思路是用一个temp记录局部最优值，用ans记录全局最优值。然后在每次for循环进行一个判断：当前遍历元素+temp值是否大于当前遍历元素的值，如果大于，说明temp值是帮了正忙的，所以让temp += 当前元素值；如果小于，说明temp是帮

2024年02月15日
浏览(37)
LeetCode[53]最大子数组和

Description: 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。解法1：遍历--超时，内存超限，不通过，算法复杂度O(n^3)了吧解法2：动态规划这里有个关键状态转移方程的定义

2024年01月25日
浏览(49)
Leetcode 子序列 53 392 115 583

1.双指针 2.动态规划初始化：这里感觉对我来说有点难以理解 dp[i][0] 这里我的理解是，以下标i-1位结尾的s和空集能够相同的子序列的个数，那么肯定只有一个，就是把s里的全部删掉 dp[0][j]s是空数组所以不可能和t一样（除了t是空数组的时候，所以dp[0][0]为1）注意：这里不

2024年02月13日
浏览(38)
动态规划——最大子数组和(Leetcode 53)

解题代码： ===== int maxSubArray(int* nums, int numsSize){ int pre = 0, maxAns = nums[0]; 自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训

2024年04月26日
浏览(37)
LeetCode:53. 最大子数组和 - Python

53. 最大子数组和问题描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。提示

2024年02月11日
浏览(34)
【LeetCode每日一题】53. 最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/ 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。先算出数组的前缀和，然后通过2个for循环遍历出所有的连续子数组。寻找一个具有

2024年02月04日
浏览(51)
【LeetCode力扣】189 53 轮转数组 | 最大子数组和

目录 1、189. 轮转数组 1.1、题目介绍 1.2、解题思路 2、53. 最大子数组和 2.1、题目介绍 2.2、解题思路原题链接： 189. 轮转数组 - 力扣（LeetCode）示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转

2024年02月08日
浏览(36)