Maximum Product Subarray (M)
題目
Given an integer array nums, 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 subarray.
題意
在給定陣列中找到一個子陣列，使其積最大，
思路
動態規劃，sm[i]表示以nums[i]為結尾的子陣列能得到的最小乘積，lg[i]表示以nums[i]為結尾的子陣列能得到的最大乘積，可以得到遞推式：
\[sm[i]=min(nums[i],\ nums[i]*sm[i-1],\ nums[i]*lg[i-1])\\ lg[i]=max(nums[i],\ nums[i]*sm[i-1],\ nums[i]*lg[i-1]) \]代碼實作
Java
class Solution {
public int maxProduct(int[] nums) {
int ans = nums[0];
int[] sm = new int[nums.length];
int[] lg = new int[nums.length];
sm[0] = nums[0];
lg[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sm[i] = Math.min(nums[i], Math.min(nums[i] * sm[i - 1], nums[i] * lg[i - 1]));
lg[i] = Math.max(nums[i], Math.max(nums[i] * sm[i - 1], nums[i] * lg[i - 1]));
ans = Math.max(ans, lg[i]);
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/16231.html
標籤：其他
下一篇：替換空格