normalmemory will cause TLE because the array can get really big.
- The tricky thing about
productis that if
dp[i-1]is really negative and really small, but
nums[i] < 0. It might even be the
maxthat we want.
- So, we not only need to record
max from 0 to i - 1, but also
MIN productending with
MAX productending with
- It’s also easy to get:
dp[i] = Math.min(nums[i], dp[i - 1]*nums[i], dp[i - 1]*nums[i]).
dp[i] = Math.max(nums[i], dp[i - 1]*nums[i], dp[i - 1]*nums[i]).
Given an integer array
nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
guaranteed that the answer will fit in a 32-bit integer.
subarray is a contiguous subsequence of the array.
Input: nums = [2,3,-2,4]
Brute Force - Heap out of memory when nums is too long