Original problem – https://leetcode.com/problems/maximum-subarray/
Original problem – https://leetcode.com/problems/maximum-product-subarray/
Additional materials
https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane’s_algorithm
Problem definition. 53. Maximum Subarray
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
Constraints:
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
Problem definition. 152. Maximum Product Subarray
Given an integer array nums
, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
- The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Solution
It’s better to start with the first problem because for that we do not need to track negative numbers. In order to solve it we could use a brute force approach (eg. on the interview we could not come up with a better approach). This involves 2 inner loops. For each entry in the array (the outer loop) we go over all the elements (inner loop) and calculate it’s value.
Normally, when the question asks to find the minimum or the maximum of something we probably could consider dynamic programming. For this specific problem, we need to track the current maximum and at some point, we simply need to restart our calculation if some of the conditions are met.
For that we need two variables: bestSum – is a result of the function and current – is a current best value. On each iteration, we keep tracking the current value and if the current digit is greater than whatever we have stored in the current var + current digit (i`th element) then we need to start over to track the subarray for the beginning.
Difference with the product
When we need to find a maximum product we have to consider minimum value as well (and also a 0). We need to do that because it might happen that the array might have an even number of negative digits which the product might give us a better result. For that case, we should use 3 variables: result, current min, and current max;
Knowing that on each iteration we have to consider the biggest value from the current value, so far maximum value and so far minimum value. For example consider following array:
-2 | 3 | -4 |
On the first iteration:
I-th = -2; current max = -2; current min = -2; result = -2
2-nd iteration:
I-th = 3; current max = 3 (3 || -2 * 3 || -2 * 3); current min = -6 ( 3 || -2 * 3 || -2 *3); result = 3 (-2 || current max = 3)
3-rd iteration:
I-th = -4; current max = 24 (-4 || 3 * -4 || -6 * -4); current min = -12 (-4 || 3 * -4 || -6 * -4); result = 24 (3 || current max = 24)
for (var i = 1; i < nums.length; i++) { int current = nums[i]; int tempMax = Math.max(current, Math.max(current * currentMax, current * currentMin)); currentMin = Math.min(current, Math.min(current * currentMax, current * currentMin)); currentMax = tempMax; result = Math.max(result, currentMax); }