动态规划求最大子序列的乘积（含负数）

整个过程是遍历数组，时间复杂度为O(n)

设f(n)为[0,n]区间内以n结尾的最大乘积

g(n)表示[0,n]区间内以n结尾的最小乘积

为什么设定g(n)：因为当这个最小乘积为负数时,遍历到的当前数也是一个负数，相乘后会得到一个较大的数。我们得考虑这个数是否为最大

状态转移方程为：

f(n)=max(f(n-1)×a[n],a[n],g(n-1)×a[n])：所有的可能性都要考虑到，特别是g(n-1)×a[n]

g(n)=min(f(n-1)×a[n],a[n],g(n-1)×a[n])：当a[n]为负数时，f(n-1)×a[n]是最小的（假设f(n-1)为正数）

代码如下：

public class MaxProduct {
    //这是主要的函数
    public static int maxProduct(int[] nums) {
        //进行初始化
        int maxSoFar = nums[0];//表示f(n)
        int minSoFar = nums[0];//表示g(n)
        int result = nums[0];
        //整个过程其实就是遍历数组，不要想的太复杂，不理解动态规划就把它当成遍历数组就好
        for (int i = 1; i < nums.length; i++) {
            int tempMax = Math.max(nums[i], Math.max(maxSoFar * nums[i], minSoFar * nums[i]));
            minSoFar = Math.min(nums[i], Math.min(maxSoFar * nums[i], minSoFar * nums[i]));
            maxSoFar = tempMax;
            result = Math.max(result, maxSoFar);
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {-2, 3, 0, 4, -2,-1,3,6};
        System.out.println(maxProduct(nums));
    }
}

希望可以帮助到你