程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode]Maximum Product Subarray

[LeetCode]Maximum Product Subarray

編輯:C++入門知識

[LeetCode]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.

這道題是找出數組中的一個子序列,要求這個子序列中數的乘積是所有子序列中最大的。

如果不考慮效率與優化問題,可以直接將所有子序列的組合列舉出來,分別求它們的積,取最大值。如下:

int maxProduct(int A[], int n) {
        int i = 0, j = 0,k=0;
        int ans = 0;
        int product = 0;
        for (i = n; i > 0; i--){
            for (j = 0; j <= n-i; j++){
                for (k = j; k < i; k++){
                    product += A[k];
                }
                if (product>ans){
                    ans = product;
                }
                product = 0;
            }
        }
        return ans;
    }

但是這樣的效率是很低的。換個思路可以想到,這道題就是一維動態規劃中的“局部最優與全局最優”。所以需要維護兩個變量,當前位置連續乘積的最大值curMax和最小值curMin。

最大值與最小值由以下三種情況可以得到:上一次的curMax*A[i],上一次的curMin*A[i],A[i]本身。如下:

int maxProduct(int A[], int n) {
        int ans = A[0];
        int curMin = A[0];
        int curMax = A[0];
        int cur = 1;
        for (int i = 1; i < n; i++){
            cur = curMax;
            curMax = max(max(A[i],A[i]*curMax),A[i]*curMin);
            curMin = min(min(A[i], A[i] * cur), A[i] * curMin);
            ans = max(ans, curMax);
        }
        return ans;
    }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved