网站建设公众号开,网站建设哪家性价比高,平度建设局网站,做网站推广怎么跟客户沟通剑指 Offer 42. 连续子数组的最大和
难度#xff1a;easy\color{Green}{easy}easy 题目描述
输入一个整型数组#xff0c;数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums [-2,1,-3,4,-1,2,1,-5,4]
输…剑指 Offer 42. 连续子数组的最大和
难度easy\color{Green}{easy}easy 题目描述
输入一个整型数组数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为 6。提示
1arr.length1051 arr.length 10^51arr.length105−100arr[i]100-100 arr[i] 100−100arr[i]100
注意本题与主站 53 题相同https://leetcode-cn.com/problems/maximum-subarray/ 算法
常见解法时间复杂度暴力搜索O(n2)O(n^2)O(n2)分治思想O(nlogn)O(nlogn)O(nlogn)动态规划O(n)O(n)O(n)
(动态规划)
状态定义 设动态规划列表 dpdpdp dp[i]dp[i]dp[i] 代表以元素 nums[i]nums[i]nums[i] 为结尾的连续子数组最大和。 为何定义最大和 dp[i] 中必须包含元素 nums[i] 保证 dp[i] 递推到 dp[i1] 的正确性如果不包含 nums[i] 递推时则不满足题目的 连续子数组 要求。 转移方程 若 dp[i−1]≤0dp[i−1]≤0dp[i−1]≤0 说明 dp[i−1]dp[i−1]dp[i−1] 对 dp[i]dp[i]dp[i] 产生负贡献即 dp[i−1]nums[i]dp[i−1]nums[i]dp[i−1]nums[i] 还不如 nums[i]nums[i]nums[i] 本身大。 当 dp[i−1]0dp[i−1]0dp[i−1]0 时执行 dp[i]dp[i−1]nums[i]dp[i]dp[i−1]nums[i]dp[i]dp[i−1]nums[i] 当 dp[i−1]≤0dp[i−1]≤0dp[i−1]≤0 时执行 dp[i]nums[i]dp[i]nums[i]dp[i]nums[i] 初始状态 dp[0]nums[0]dp[0]nums[0]dp[0]nums[0]即以 nums[0]nums[0]nums[0] 结尾的连续子数组最大和为 nums[0]nums[0]nums[0] 。 返回值 返回 dpdpdp 列表中的最大值代表全局最大值。 复杂度分析 时间复杂度O(n)O(n)O(n)。 空间复杂度 : O(1)O(1)O(1)
C 代码
使用 res 代表最终的答案s 表示前 i - 1 项的值 如果前 i - 1 项的值小于 0s 等于当前的数 num如果大于 0 说明可以加上当前的数字 num继续往后运算。
class Solution {
public:int maxSubArray(vectorint nums) {int res INT_MIN, s 0;for (auto x : nums) {if (s 0) s 0;s x;res max(res, s);}return res;}
};参考链接
