leetcode 53 Maximum Subarray

xiaoxiao2021-02-28  10

leetcode 53 Maximum Subarray

给定一个数组(至少包含一个整数),找出一个该数组的连续子数组,并且该连续子数组的和最大,返回最大值。

算法

同样使用动态规划解题,找出状态n和n-1之间的关系,然后从0到n-1遍历一遍得到结果

状态n和n-1的关系

在每个状态下记录两个值,一个是当前的最大值largest,一个是当前的连续子数组的和nowsum

nowsum(n)=nums[n] nowsum(n-1)<0,

​ nowsum(n-1)+nums[n] nowsum(n-1)>=0.

largest(n)=max(largest(n-1), nowsum(n)).

初始状态

largest(0)=nowsum(0)=nums[0].

code

class Solution { public: int maxSubArray(vector<int>& nums) { int largestsum = nums[0], nowsum = nums[0]; for (int i = 1; i < nums.size(); i++){ if(nowsum<0){ nowsum = nums[i]; } else{ nowsum += nums[i]; } largestsum = max(largestsum, nowsum); } return largestsum; } };

算法时间复杂度: O(n)

转载请注明原文地址: https://www.6miu.com/read-2000322.html

最新回复(0)