Dynamic Programming - Subarray

Contiguous Subarray

Maximum Sum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

1
2
3
4
// sum[i] : max sum of subarray end with nums[i]

sum[i] = nums[i] + (sum[i-1] > 0 ? sum[i-1] : 0);
res = max(res, sum[i]);

Maximum Product Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest product and return its product.

Considering that the product of two negative numbers can be bigger than two positive numbers, compared to the ‘maximum sum subarray’ problem, we save two intermediate results, thus min and max product of subarraies end with nums[i].

1
2
3
4
5
6
// maxi[i] : max product of subarray end with nums[i]
// mini[i] : min product of subarray end with nums[i] (including negative)

maxi[i] = max( maxi[i-1]*nums[i], mini[i-1]*nums[i], nums[i] );
mini[i] = min( maxi[i-1]*nums[i], mini[i-1]*nums[i], nums[i] );
res = max(res, maxi[i]);

Number of Subarraies that Sum Equals K

Array contains both positive and negative numbers.

Number of Subarraies that Product Less Than K

All posivite numbers.

This is a two-pointer/sliding-window problem. The idea is always keep an max-product-window less than K.

1
2
3
4
shift window by adding a new number on the right;
while (the product is greater than K)
then try to reduce numbers on the left ;
introduce `size of window` new subarrays;

For window (5, 2), when 6 is introduced, it add 3 new subarray: {5}, {5, 2}, {5, 2, 6}.

1
2
3
4
5
6
7
for (int left = 0, right = 0; j < nums.size(); right++) {
prod *= nums[right];
while (left <= right && prod >= K) {
prod /= nums[left++];
}
counter += right - left + 1;
}

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Discontinuous Subarray

Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

1
2
3
4
5
for (j = 3; j > 0; --j) {
if (f[0][j - 1] == INT_MIN) continue;
f[0][j] = max(f[0][j], max(f[0][j - 1] * nums[i], f[1][j - 1] * nums[i]));
f[1][j] = min(f[1][j], min(f[0][j - 1] * nums[i], f[1][j - 1] * nums[i]));
}