首页 > 代码库 > LeetCode Maximum Product Subarray
LeetCode Maximum Product Subarray
class Solution {public: int maxProduct(int A[], int n) { if (A == NULL || n < 1) { return INT_MIN; } int res = INT_MIN; int tr = 1; for (int i=0; i<n; i++) { tr = tr * A[i]; if (tr > res) { res = tr; } if (tr == 0) { tr = 1; } } tr = 1; for (int i=n-1; i>=0; i--) { tr = tr * A[i]; if (tr > res) { res = tr; } if (tr == 0) { tr = 1; } } return res; }};
更叼的方法,不过速度上没有明显提升
class Solution {public: int maxProduct(int A[], int n) { // store the result that is the max we have found so far int r = A[0]; // imax/imin stores the max/min product of // subarray that ends with the current number A[i] for (int i = 1, imax = r, imin = r; i < n; i++) { // multiplied by a negative makes big number smaller, small number bigger // so we redefine the extremums by swapping them if (A[i] < 0) swap(imax, imin); // max/min product for the current number is either the current number itself // or the max/min by the previous number times the current one imax = max(A[i], imax * A[i]); imin = min(A[i], imin * A[i]); // the newly computed max value is a candidate for our global result r = max(r, imax); } return r; }};
LeetCode Maximum Product Subarray
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。