Kadane’s algorithm
Maximum subarray problem
Maximum Subarray
1
2
3
4
5
6
7
8
9
| public int maxSubArray(int[] nums) {
int max = nums[0], currSum = nums[0];
for (int i = 1; i < nums.length; i++) {
// currSum is the max sum ending at num
currSum = nums[i] + Math.max(currSum, 0);
max = Math.max(max, currSum);
}
return max;
}
|
This can be viewed as a simple/trivial example of dynamic programming.
Similarly, we can apply the same method to find min subarrays:
Maximum Sum Circular Subarray
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int maxSubarraySumCircular(int[] nums) {
int sum = 0, maxSum = nums[0], minSum = nums[0], currMax = 0, currMin = 0;
for (int num : nums) {
currMax = Math.max(currMax + num, num);
maxSum = Math.max(maxSum, currMax);
currMin = Math.min(currMin + num, num);
minSum = Math.min(minSum, currMin);
sum += num;
}
// corner case: if all numbers are negative,
// maxSum == max(nums) and minSum = sum(nums), max(maxSum, total - minSum) == 0
// i.e. empty subarray.
// we need to return max(nums) instead
return maxSum > 0 ? Math.max(maxSum, sum - minSum) : maxSum;
}
|
Maximum Score Of Spliced Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int maximumsSplicedArray(int[] nums1, int[] nums2) {
// finds the maximum subarray of nums2 - nums1 into nums1
// or nums1 - nums2 into nums2
int sum1 = 0, sum2 = 0, currSum1 = 0, currSum2 = 0, max1 = 0, max2 = 0;
for (int i = 0; i < nums1.length; i++) {
sum1 += nums1[i];
sum2 += nums2[i];
currSum1 = nums2[i] - nums1[i] + Math.max(currSum1, 0);
currSum2 = nums1[i] - nums2[i] + Math.max(currSum2, 0);
max1 = Math.max(max1, currSum1);
max2 = Math.max(max2, currSum2);
}
return Math.max(sum1 + max1, sum2 + max2);
}
|
Maximum Product Subarray
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int maxProduct(int[] nums) {
int max = nums[0], min = nums[0];
int product = max;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int tmp = max;
max = min;
min = tmp;
}
max = Math.max(nums[i], max * nums[i]);
min = Math.min(nums[i], min * nums[i]);
product = Math.max(product, max);
}
return product;
}
|
Maximum Alternating Subarray Sum
1
2
3
4
5
6
7
8
9
10
| public long maximumAlternatingSubarraySum(int[] nums) {
long max = nums[0], neg = 0, pos = nums[0];
for (int i = 1; i < nums.length; i++) {
long tmp = neg;
neg = pos - nums[i];
pos = Math.max(0, tmp) + nums[i];
max = Math.max(max, Math.max(neg, pos));
}
return max;
}
|
Maximum Subarray Sum After One Operation
1
2
3
4
5
6
7
8
9
10
11
12
| public int maxSumAfterOperation(int[] nums) {
int n = nums.length;
int[][] dp = new int[n + 1][2];
int max = 0;
for (int i = 0; i < n; i++) {
dp[i + 1][0] = nums[i] + Math.max(dp[i][0], 0);
dp[i + 1][1] = Math.max(dp[i][0] + nums[i] * nums[i], dp[i][1] + nums[i]);
dp[i + 1][1] = Math.max(dp[i + 1][1], nums[i] * nums[i]);
max = Math.max(max, dp[i + 1][1]);
}
return max;
}
|
Reduced to 1D:
1
2
3
4
5
6
7
8
9
| public int maxSumAfterOperation(int[] nums) {
int op = 0, noop = 0, max = 0;
for (int num : nums) {
op = Math.max(num * num, Math.max(noop + num * num, op + num));
noop = num + Math.max(noop, 0);
max = Math.max(max, op);
}
return max;
}
|
Maximum Subarray Sum with One Deletion
1
2
3
4
5
6
7
8
9
10
| public int maximumSum(int[] arr) {
int n = arr.length;
int oneDelete = 0, noDelete = arr[0], max = arr[0];
for (int i = 1; i < n; i++) {
oneDelete = Math.max(oneDelete + arr[i], noDelete);
noDelete = Math.max(noDelete + arr[i], arr[i]);
max = Math.max(max, Math.max(oneDelete, noDelete));
}
return max;
}
|
Best Time to Buy and Sell Stock
1
2
3
4
5
6
7
8
| public int maxProfit(int[] prices) {
int max = 0, curr = 0;
for (int i = 1; i < prices.length; i++) {
curr = Math.max(0, curr += prices[i] - prices[i - 1]);
max = Math.max(curr, max);
}
return max;
}
|
1
2
3
4
5
6
7
8
| public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, profit = 0;
for (int p : prices) {
minPrice = Math.min(p, minPrice);
profit = Math.max(profit, p - minPrice);
}
return profit;
}
|
Best Sightseeing Pair
1
2
3
4
5
6
7
8
| public int maxScoreSightseeingPair(int[] A) {
int max = 0, curr = 0;
for (int i = 0; i < A.length; i++) {
max = Math.max(max, curr + A[i] - i);
curr = Math.max(curr, A[i] + i);
}
return max;
}
|
1
2
3
4
5
6
7
8
9
10
| public int maxScoreSightseeingPair(int[] A) {
int max = 0, curr = 0;
for (int a : A) {
max = Math.max(max, curr + a);
// curr is the best score so far
// all spots by far are 1 distance further
curr = Math.max(curr, a) - 1;
}
return max;
}
|
Number of Subarrays with Bounded Maximum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int numSubarrayBoundedMax(int[] nums, int left, int right) {
int count = 0;
int dp = 0; // number of valid subarrays ending at nums[i]
int prev = -1; // index of the last num which is > right
for (int i = 0; i < nums.length; i++) {
if (nums[i] > right) {
dp = 0;
prev = i;
} else if (nums[i] >= left) {
// all nums in (prev, i] is in range
dp = i - prev;
}
// if nums[i] < left, appends it to the current dp array,
// and it won't change the max of the dp array
// so dp[i] == dp[i - 1] (nums[]i] itself is out of range)
count += dp;
}
return count;
}
|
Time Needed to Rearrange a Binary String
1
2
3
4
5
6
7
8
9
10
11
| public int secondsToRemoveOccurrences(String s) {
int zeros = 0, seconds = 0;
for (char ch : s.toCharArray()) {
zeros += '1' - ch;
if (ch == '1' && zeros > 0) {
// the time update is possible only at '1'
seconds = Math.max(seconds + 1, zeros);
}
}
return seconds;
}
|
Substring With Largest Variance
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
| public int largestVariance(String s) {
Set<Character> chars = s.chars().mapToObj(ch -> (char)ch).collect(Collectors.toSet());
int max = 0;
// the order is ch1 then ch2, and ch1 increases variance while ch2 decreases it
// i.e. ch1 == 'a', ch2 == 'b' is different from ch1 == 'b', ch1 == 'a'
for (char ch1 : chars) {
for (char ch2 : chars) {
int variance = 0;
boolean hasCh2 = false, isFirstCharCh2 = false;
for (char ch : s.toCharArray()) {
// +1 if it's ch1
if (ch == ch1) {
variance++;
}
if (ch == ch2) {
hasCh2 = true;
if (isFirstCharCh2 && variance >= 0) {
// if the substring starts with ch2, we trim the leading ch2 when we encounter another ch2
// the variance is not affected
// e.g. "bab" -> "ab", "baab" -> "aab"
isFirstCharCh2 = false;
} else if (--variance < 0) {
// -1 if it's ch2
// if doing so makes variance negative, restarts from the current position
// e.g. "abb" -> "b", "aabbb" -> "b"
isFirstCharCh2 = true;
variance = -1;
}
}
// if there are less than 2 chars, the variance is 0
max = Math.max(max, hasCh2 ? variance : 0);
}
}
}
return max;
}
|
This problem has a more intuitive prefix sum solution.
2D
Max Dot Product of Two Subsequences
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| private static final int MIN_DOT_PRODUCT = -(int)5e8;
public int maxDotProduct(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 0; i <= n1; i++) {
Arrays.fill(dp[i], MIN_DOT_PRODUCT);
}
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
dp[i][j] = Math.max(nums1[i - 1] * nums2[j - 1],
Math.max(dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1],
Math.max(dp[i - 1][j], dp[i][j - 1])));
}
}
return dp[n1][n2];
}
|
Cumulative
Reducing Dishes
1
2
3
4
5
6
7
8
9
10
| public int maxSatisfaction(int[] satisfaction) {
Arrays.sort(satisfaction);
int max = 0, total = 0;
for (int i = satisfaction.length - 1; i >= 0 && satisfaction[i] > -total; i--) {
// cumulative
max += total += satisfaction[i];
}
return max;
}
|