解题思路

这是一个动态规划问题，但需要同时维护最大值和最小值，因为：

  1. 当遇到负数时，最小值乘以负数可能变成最大值
  2. 当遇到正数时，最大值乘以正数仍然是最大值
  3. 当遇到0时，需要重新开始计算

具体步骤：

  1. 维护两个 数组： 和
  2. 表示以 结尾的子数组的最大乘积
  3. 表示以 结尾的子数组的最小乘积
  4. 遇到新的数时，需要考虑三种情况：
    • 当前数自己
    • 当前数乘以之前的最大值
    • 当前数乘以之前的最小值

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) return 0;
    
    int maxDP = nums[0];
    int minDP = nums[0];
    int result = nums[0];
    
    for(int i = 1; i < n; i++) {
        int temp = maxDP;
        maxDP = max({nums[i], maxDP * nums[i], minDP * nums[i]});
        minDP = min({nums[i], temp * nums[i], minDP * nums[i]});
        result = max(result, maxDP);
    }
    
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << maxProduct(nums) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int maxProduct(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        
        int maxDP = nums[0];
        int minDP = nums[0];
        int result = nums[0];
        
        for(int i = 1; i < n; i++) {
            int temp = maxDP;
            maxDP = Math.max(nums[i], 
                    Math.max(maxDP * nums[i], minDP * nums[i]));
            minDP = Math.min(nums[i], 
                    Math.min(temp * nums[i], minDP * nums[i]));
            result = Math.max(result, maxDP);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(maxProduct(nums));
        sc.close();
    }
}

def max_product(nums):
    if not nums:
        return 0
        
    max_dp = nums[0]
    min_dp = nums[0]
    result = nums[0]
    
    for i in range(1, len(nums)):
        temp = max_dp
        max_dp = max(nums[i], max_dp * nums[i], min_dp * nums[i])
        min_dp = min(nums[i], temp * nums[i], min_dp * nums[i])
        result = max(result, max_dp)
    
    return result

n = int(input())
nums = list(map(int, input().split()))
print(max_product(nums))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，只需要遍历一次数组
  • 空间复杂度：，只使用了常数个变量