#Problem

#⭐️⭐️⭐️⭐️⭐️

Maximum subarray的follow up. 在可循环的array里找maximum subarray sum.

#Solution

神题

分两种情况考虑:

  1. Max sum不用循环, 跟Maximum subarray一样用kadane’s algorithm直接可以解决.
  2. Max sum需要循环, 那么可以证明除去Max Sum包含的元素, 剩余元素:
    • 肯定不会循环.
    • 肯定是Minimum subarray sum.
    • 因此解法就是用Kadane’s Algorithm做minimum subarray sum, 然后total sum - min sum即使循环的maximum sum.

另外还要特别注意两点优化:

  • 如果array全是positive number或者全是negative number, 做一遍kadane即可.

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public int maxSubarraySumCircular(int[] A) {
boolean allPositive = true;
boolean allNegative = true;
for (int num : A) {
if (num < 0) allPositive = false;
else if (num >= 0) allNegative = false;
}
int maxKadane = maxKadane(A);
int minKadane = minKadane(A);
if (allPositive || allNegative) return maxKadane;
int sum = 0;
for (int num : A) sum += num;
return Math.max(maxKadane, sum - minKadane);
}
private int maxKadane(int[] A) {
int res = Integer.MIN_VALUE;
int sumEndHere = 0;
for (int num : A) {
sumEndHere = Math.max(num, sumEndHere + num);
res = Math.max(res, sumEndHere);
}
return res;
}
private int minKadane(int[] A) {
int res = Integer.MAX_VALUE;
int sumEndHere = 0;
for (int num : A) {
sumEndHere = Math.min(sumEndHere + num, num);
res = Math.min(res, sumEndHere);
}
return res;
}
}

Comments