Formatted question description: https://leetcode.ca/all/152.html
Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. Example 2: Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a continuous subarray. @tag-array
Do it with DP, and use two dp arrays,
- Where f[i] represents the largest sub-array product within the range of sub-array [0, i] and must contain nums[i] numbers,
- g[i] represents the smallest sub-array product within the range of sub-array [0, i] and must contain nums[i] numbers, During initialization, both f and g are initialized to nums, and the rest are initialized to 0.
Starting from the second number of the array, the maximum and minimum values at this time will only be generated between these three numbers, that is
- And nums[i].
So use the maximum of the three to update f[i], use the minimum to update g[i], and then use f[i] to update the result.
Since the final result may not include the number nums[n-1], f[n-1] is
not necessarily the final solution, and the constantly updated result is to be retuened.