[leetcode] 918. Maximum Sum Circular Subarray

[leetcode] 918. Maximum Sum Circular Subarray

Description

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]Output: 3Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]Output: 10Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]Output: 4Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]Output: 3Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]Output: -1Explanation: Subarray [-1] has maximum sum -1

Note:

-30000 <= A[i] <= 300001 <= A.length <= 30000

分析

题目的意思是：求一个循环数组的子序列和的最大值，代码一是我自己包里破解的，分了三种情况，所有的都为负，所有的都为正，有正也有负。比较死板。 代码二就厉害了，用了动态规划，一个循环就搞定了,

dp[j]=max(A[i],A[i+1],...,A[j])

dp[j+1]=A[j+1]+max(dp[j],0)

大概意思dp[j]就定义为A[i]~A[j]最大的和，考虑到dp[j]可能为负数，所以最后公式就变成了dp[j+1]=A[j+1]+max(dp[j],0)了

代码一

class Solution: def maxSubarraySumCircular(self, A: List[int]) -> int: max_value=float("-inf") t=0 flag=True for i in range(len(A)): if(A[i]<0): flag=False break t+=A[i] if(flag): return t for i in range(len(A)): sum_a=0 if(A[i]>0): sum_a=0 for j in range(i,i+len(A)): a=j%len(A) sum_a+=A[a] max_value=max(sum_a,max_value) if(sum_a<0): break if(max_value==float("-inf")): for i in range(len(A)): max_value=max(max_value,A[i]) return max_value

代码二

class Solution: def maxSubarraySumCircular(self, A: List[int]) -> int: ans=cur=0 for x in A: cur=x+max(cur,0) ans=max(ans,cur) return ans

参考文献

​​[LeetCode]Notes and A Primer on Kadane’s Algorithm​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。