首页 > 代码库 > Leetcode | Maximum Product Subarray
Leetcode | Maximum Product Subarray
Leetcode 加新题了
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.
整理思路不难，就是维护一个包含当前位置的最大正数和最小负数。在处理负数的时候需要注意。
1 class Solution { 2 public: 3 int maxProduct(int arr[], int n) { 4 if (n <= 0) return 0; 5 int maxPos = 1, minNeg = 1, max = INT_MIN; 6 for (int i = 0; i < n; ++i) { 7 if (arr[i] > 0) { 8 maxPos = maxPos * arr[i]; 9 minNeg = minNeg > 0 ? 1: minNeg * arr[i];10 if (maxPos > max) max = maxPos;11 } else if (arr[i] == 0) {12 maxPos = minNeg = 1;13 if (max < 0) max = 0;14 } else { // arr[i] < 015 int tmp = maxPos;16 if (minNeg > 0) {17 maxPos = 1;18 } else {19 maxPos = minNeg * arr[i];20 if (maxPos > max) max = maxPos;21 }22 minNeg = tmp * arr[i];23 if (minNeg > max) max = minNeg;24 }25 }26 return max;27 }28 };
看了一下solution之后，还有更简洁的写法。我还是好弱。每天都能学到新东西啊。
1 class Solution { 2 public: 3 int maxProduct(int arr[], int n) { 4 if (n <= 0) return 0; 5 int maxSoFar = arr[0], minSoFar = arr[0], ans = arr[0]; 6 for (int i = 1; i < n; ++i) { 7 int tmp = maxSoFar; 8 maxSoFar = max(max(arr[i], maxSoFar * arr[i]), minSoFar * arr[i]); 9 minSoFar = min(min(arr[i], tmp * arr[i]), minSoFar * arr[i]);10 if (maxSoFar > ans) ans = maxSoFar;11 }12 return ans;13 }14 };
Leetcode | Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。