Queue
Array
Divide and Conquer
Dynamic Programming
Monotonic Queue
Description
Given a circular integer array nums
of length n
, return the maximum possible sum of a non-empty subarray of nums
.
A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i]
is nums[(i + 1) % n]
and the previous element of nums[i]
is nums[(i - 1 + n) % n]
.
A subarray may only include each element of the fixed buffer nums
at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j]
, there does not exist i <= k1
, k2 <= j
with k1 % n == k2 % n
.
Example 1:
Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.
Example 2:
Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
Example 3:
Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.
Constraints:
n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def maxSubarraySumCircular ( self , nums : List [ int ]) -> int :
s1 = s2 = f1 = f2 = nums [ 0 ]
for num in nums [ 1 :]:
f1 = num + max ( f1 , 0 )
f2 = num + min ( f2 , 0 )
s1 = max ( s1 , f1 )
s2 = min ( s2 , f2 )
return s1 if s1 <= 0 else max ( s1 , sum ( nums ) - s2 )
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public int maxSubarraySumCircular ( int [] nums ) {
int s1 = nums [ 0 ] , s2 = nums [ 0 ] , f1 = nums [ 0 ] , f2 = nums [ 0 ] , total = nums [ 0 ] ;
for ( int i = 1 ; i < nums . length ; ++ i ) {
total += nums [ i ] ;
f1 = nums [ i ] + Math . max ( f1 , 0 );
f2 = nums [ i ] + Math . min ( f2 , 0 );
s1 = Math . max ( s1 , f1 );
s2 = Math . min ( s2 , f2 );
}
return s1 > 0 ? Math . max ( s1 , total - s2 ) : s1 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
int maxSubarraySumCircular ( vector < int >& nums ) {
int s1 = nums [ 0 ], s2 = nums [ 0 ], f1 = nums [ 0 ], f2 = nums [ 0 ], total = nums [ 0 ];
for ( int i = 1 ; i < nums . size (); ++ i ) {
total += nums [ i ];
f1 = nums [ i ] + max ( f1 , 0 );
f2 = nums [ i ] + min ( f2 , 0 );
s1 = max ( s1 , f1 );
s2 = min ( s2 , f2 );
}
return s1 > 0 ? max ( s1 , total - s2 ) : s1 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 func maxSubarraySumCircular ( nums [] int ) int {
s1 , s2 , f1 , f2 , total := nums [ 0 ], nums [ 0 ], nums [ 0 ], nums [ 0 ], nums [ 0 ]
for i := 1 ; i < len ( nums ); i ++ {
total += nums [ i ]
f1 = nums [ i ] + max ( f1 , 0 )
f2 = nums [ i ] + min ( f2 , 0 )
s1 = max ( s1 , f1 )
s2 = min ( s2 , f2 )
}
if s1 <= 0 {
return s1
}
return max ( s1 , total - s2 )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function maxSubarraySumCircular ( nums : number []) : number {
let pre1 = nums [ 0 ],
pre2 = nums [ 0 ];
let ans1 = nums [ 0 ],
ans2 = nums [ 0 ];
let sum = nums [ 0 ];
for ( let i = 1 ; i < nums . length ; ++ i ) {
let cur = nums [ i ];
sum += cur ;
pre1 = Math . max ( pre1 + cur , cur );
ans1 = Math . max ( pre1 , ans1 );
pre2 = Math . min ( pre2 + cur , cur );
ans2 = Math . min ( pre2 , ans2 );
}
return ans1 > 0 ? Math . max ( ans1 , sum - ans2 ) : ans1 ;
}
Solution 2
Python3 Java C++ Go TypeScript
class Solution :
def maxSubarraySumCircular ( self , nums : List [ int ]) -> int :
pmi , pmx = 0 , - inf
ans , s , smi = - inf , 0 , inf
for x in nums :
s += x
ans = max ( ans , s - pmi )
smi = min ( smi , s - pmx )
pmi = min ( pmi , s )
pmx = max ( pmx , s )
return max ( ans , s - smi )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public int maxSubarraySumCircular ( int [] nums ) {
final int inf = 1 << 30 ;
int pmi = 0 , pmx = - inf ;
int ans = - inf , s = 0 , smi = inf ;
for ( int x : nums ) {
s += x ;
ans = Math . max ( ans , s - pmi );
smi = Math . min ( smi , s - pmx );
pmi = Math . min ( pmi , s );
pmx = Math . max ( pmx , s );
}
return Math . max ( ans , s - smi );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public :
int maxSubarraySumCircular ( vector < int >& nums ) {
const int inf = 1 << 30 ;
int pmi = 0 , pmx = - inf ;
int ans = - inf , s = 0 , smi = inf ;
for ( int x : nums ) {
s += x ;
ans = max ( ans , s - pmi );
smi = min ( smi , s - pmx );
pmi = min ( pmi , s );
pmx = max ( pmx , s );
}
return max ( ans , s - smi );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13 func maxSubarraySumCircular ( nums [] int ) int {
const inf = 1 << 30
pmi , pmx := 0 , - inf
ans , s , smi := - inf , 0 , inf
for _ , x := range nums {
s += x
ans = max ( ans , s - pmi )
smi = min ( smi , s - pmx )
pmi = min ( pmi , s )
pmx = max ( pmx , s )
}
return max ( ans , s - smi )
}
1
2
3
4
5
6
7
8
9
10
11
12
13 function maxSubarraySumCircular ( nums : number []) : number {
const inf = 1 << 30 ;
let [ pmi , pmx ] = [ 0 , - inf ];
let [ ans , s , smi ] = [ - inf , 0 , inf ];
for ( const x of nums ) {
s += x ;
ans = Math . max ( ans , s - pmi );
smi = Math . min ( smi , s - pmx );
pmi = Math . min ( pmi , s );
pmx = Math . max ( pmx , s );
}
return Math . max ( ans , s - smi );
}
GitHub