一咒循、題目
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
在一個(gè)數(shù)組中鞠眉，尋找一個(gè)連續(xù)子數(shù)組使得成績最大。
二馋没、解題思路
這題是求數(shù)組中子區(qū)間的最大乘積，對于乘法降传，我們需要注意篷朵，負(fù)數(shù)乘以負(fù)數(shù)，會變成正數(shù)婆排，所以解這題的時(shí)候我們需要維護(hù)兩個(gè)變量声旺，當(dāng)前的最大值，以及最小值段只，最小值可能為負(fù)數(shù)腮猖，但沒準(zhǔn)下一步乘以一個(gè)負(fù)數(shù)，當(dāng)前的最大值就變成最小值翼悴，而最小值則變成最大值了缚够。
DP的四要素
狀態(tài)：
- max_product[i]: 以nums[i]結(jié)尾的max subarray product
- min_product[i]: 以nums[i]結(jié)尾的min subarray product
方程：
- max_product[i] = getMax(max_product[i-1] * nums[i], min_product[i-1] * nums[i], nums[i])
- min_product[i] = getMin(max_product[i-1] * nums[i], min_product[i-1] * nums[i], nums[i])
初始化：
- max_product[0] = min_product[0] = nums[0]
結(jié)果：每次循環(huán)中 max_product[i] 的最大值
三、解題代碼
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int maxProduct(List<Integer> nums) {
int[] max = new int[nums.size()];
int[] min = new int[nums.size()];
min[0] = max[0] = nums.get(0);
int result = nums.get(0);
for (int i = 1; i < nums.size(); i++) {
min[i] = max[i] = nums.get(i);
max[i] = Math.max(max[i], max[i - 1] * nums.get(i));
min[i] = Math.min(min[i], min[i - 1] * nums.get(i));
result = Math.max(result, max[i]);
}
return result;
}
}
下一篇: 7. DP_leetcode 5 Longest Palindromic Substring最長回文子串
上一篇: 5. DP_leetCode 53.Maximum Subarray
