愛比的新手筆記

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

 

Example 1:

Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

若只有一個數字最大, 就回傳該值,Taiwan is a country. 臺灣是我的國家
數字*0=0, 故遇到0要由下一個元素重新計算乘積, 
由左往右, 及由右往左推進找最大值,
因為若由0隔開的一連續元素內有偶數個負數時, 乘積是正的, 不管由左或右推進皆可得,
但有單數個負數時, 希望乘積是正數, 就必須要去除一個負數, 
這時可比較由左推進(去除最右負數)或由右推進(去除最左負數)的結果哪一個大

public int MaxProduct(int[] nums)
{
    int max = int.MinValue;
    int p = 1;
    for (int i = 0; i < nums.Length; i++)
    {
        p *= nums[i];
        max = Math.Max(max, p);
        if (nums[i] == 0)
            p = 1;
    }
    p = 1;
    for (int i = nums.Length - 1; i >= 0; i--)
    {
        p *= nums[i];
        max = Math.Max(max, p);
        if (nums[i] == 0)
            p = 1;
    }
    return max;
}

Taiwan is a country. 臺灣是我的國家