首页 > 代码库 > leetcode 152. Maximum Product Subarray
leetcode 152. Maximum Product Subarray
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.
使用动态规划求解：
新建三个数组suffix_min[n], suffix_max[n], global_max[n]. 分别表示包含最后元素的最小乘积，包含最后元素的最大乘积，和全局最大乘积。
假设已知suffix_min[i-1], suffix_max[i-1],
那么suffix_max[i]是suffix_max[i-1] * A[i], suffix_min[i-1]*A[i], A[i]三者中的最大值，suffix_min[i]是三者中的最小值。
而global_max[i]则是global_max[i-1]和suffix_max[i]中的最大值。
1 int maxProduct(int A[], int n) 2 { 3 if (n <= 0) 4 return n; 5 int *suffix_max = new int[n]; 6 int *suffix_min = new int[n]; 7 int *global_max = new int[n]; 8 int temp_min, temp_max, max_product; 9 10 suffix_max[0] = A[0];11 suffix_min[0] = A[0];12 global_max[0] = A[0];13 for (int i = 1; i < n; i++)14 {15 temp_min = A[i] * suffix_min[i - 1];16 temp_max = A[i] * suffix_max[i - 1];17 suffix_min[i] = min(A[i], min(temp_min, temp_max));18 suffix_max[i] = max(A[i], max(temp_min, temp_max));19 global_max[i] = max(suffix_max[i], global_max[i - 1]);20 }21 max_product = global_max[n - 1];22 delete[] suffix_max;23 delete[] suffix_min;24 delete[] global_max;25 26 return max_product;27 }
对于本题，只需要求出global_max[n]即可，实际上不需要记录全部global_max[0, ..., n -1]
1 int maxProduct(int A[], int n) 2 { 3 if (n <= 0) 4 return n; 5 int temp_min, temp_max; 6 7 int suffix_max = A[0]; 8 int suffix_min = A[0]; 9 int global_max = A[0];10 for (int i = 1; i < n; i++)11 {12 temp_min = A[i] * suffix_min;13 temp_max = A[i] * suffix_max;14 suffix_min = min(A[i], min(temp_min, temp_max));15 suffix_max = max(A[i], max(temp_min, temp_max));16 global_max = max(suffix_max, global_max);17 }18 19 return global_max;20 }
leetcode 152. Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。