java如何計算連續數字最大乘積

Java如何計算連續數字最大乘積

在編程中，計算連續數字的最大乘積是一個常見的問題。這類問題通常出現在算法競賽、面試題以及實際應用中。本文將介紹如何使用Java編寫一個高效的算法來計算連續數字的最大乘積。

問題描述

給定一個整數數組，我們需要找到數組中連續子數組的最大乘積。例如，對于數組 [2, 3, -2, 4]，連續子數組 [2, 3] 的乘積為 6，而 [4] 的乘積為 4，因此最大乘積為 6。

算法思路

要解決這個問題，我們可以使用動態規劃（Dynamic Programming）的方法。動態規劃是一種分階段解決問題的方法，它將問題分解為多個子問題，并通過保存子問題的解來避免重復計算。

動態規劃狀態定義

我們定義兩個狀態數組： - maxDP[i]：表示以第 i 個元素結尾的子數組的最大乘積。 - minDP[i]：表示以第 i 個元素結尾的子數組的最小乘積。

狀態轉移方程

對于每個元素 nums[i]，我們有以下狀態轉移方程： - 如果 nums[i] 是正數，那么 maxDP[i] 可以通過 maxDP[i-1] * nums[i] 或 nums[i] 得到。 - 如果 nums[i] 是負數，那么 maxDP[i] 可以通過 minDP[i-1] * nums[i] 或 nums[i] 得到。 - 同理，minDP[i] 也可以通過類似的方式得到。

具體來說：

maxDP[i] = Math.max(nums[i], Math.max(maxDP[i-1] * nums[i], minDP[i-1] * nums[i]));
minDP[i] = Math.min(nums[i], Math.min(maxDP[i-1] * nums[i], minDP[i-1] * nums[i]));

初始條件

對于第一個元素 nums[0]，maxDP[0] 和 minDP[0] 都等于 nums[0]。

最終結果

我們需要遍歷整個數組，并在遍歷過程中不斷更新 maxDP 和 minDP 數組。最終，maxDP 數組中的最大值就是我們要找的連續子數組的最大乘積。

Java代碼實現

public class MaxProductSubarray {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] maxDP = new int[n];
        int[] minDP = new int[n];
        maxDP[0] = nums[0];
        minDP[0] = nums[0];
        int result = nums[0];

        for (int i = 1; i < n; i++) {
            maxDP[i] = Math.max(nums[i], Math.max(maxDP[i-1] * nums[i], minDP[i-1] * nums[i]));
            minDP[i] = Math.min(nums[i], Math.min(maxDP[i-1] * nums[i], minDP[i-1] * nums[i]));
            result = Math.max(result, maxDP[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        MaxProductSubarray solution = new MaxProductSubarray();
        int[] nums = {2, 3, -2, 4};
        System.out.println("最大乘積: " + solution.maxProduct(nums)); // 輸出: 6
    }
}

代碼解釋

1. 初始化：我們首先檢查輸入數組是否為空或長度為0，如果是，則返回0。
2. 狀態數組：我們創建兩個數組 maxDP 和 minDP 來存儲以每個元素結尾的子數組的最大和最小乘積。
3. 狀態轉移：我們遍歷數組，并根據當前元素的值更新 maxDP 和 minDP 數組。
4. 結果更新：在每次更新 maxDP 和 minDP 后，我們更新最終結果 result。
5. 返回結果：遍歷結束后，result 就是我們要找的最大乘積。

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。我們只需要遍歷數組一次。
• 空間復雜度：O(n)，我們使用了兩個額外的數組 maxDP 和 minDP 來存儲中間結果。

優化空間復雜度

我們可以通過使用變量來代替數組來優化空間復雜度，將空間復雜度降低到 O(1)。

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int maxProduct = nums[0];
    int minProduct = nums[0];
    int result = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int tempMax = maxProduct;
        maxProduct = Math.max(nums[i], Math.max(maxProduct * nums[i], minProduct * nums[i]));
        minProduct = Math.min(nums[i], Math.min(tempMax * nums[i], minProduct * nums[i]));
        result = Math.max(result, maxProduct);
    }

    return result;
}

總結

通過動態規劃的方法，我們可以高效地解決連續數字最大乘積的問題。Java的實現簡潔明了，且通過優化可以將空間復雜度降低到 O(1)。希望本文能幫助你理解并掌握這一算法。