乘积最大子序列

发表于

算法：动态规划



题目

https://leetcode-cn.com/problems/maximum-product-subarray/

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。



Java解法

暴力破解

申请空间储存所有的中间结果，再拿中间结果结算下一个位置的所有结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
	public int maxProduct(int[] nums) {
		if(null==nums || nums.length==0) return 0;
		ArrayList<TreeSet<Integer>> max = new ArrayList<TreeSet<Integer>>();
		max.add(new TreeSet<Integer>());
		Integer preMax = Integer.MIN_VALUE;
		for(int i=0; i<nums.length; ++i) {
			TreeSet<Integer> curList = new TreeSet<Integer>();
			TreeSet<Integer> preList = max.get(i);
			if (preList==null || preList.size()<=0) {
				int cur = nums[i];
				curList.add(cur);
				if (preMax < cur) preMax = cur;
			} else {
				for (Integer x : preList) {
					int cur = x * nums[i];
					curList.add(cur);
					int curMax = cur>nums[i]?cur:nums[i];
					if (cur != curMax) curList.add(curMax);
					if (preMax < curMax) preMax = curMax;
				}
			}
			curList.add(nums[i]);
			max.add(curList);
		}
		return preMax;
	}
}
public class App {
	public static void main(String[] args) throws IOException {
		int x = new Solution().maxProduct(new int[]{2,3,-2,4});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{-2,0,-1});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{-2,3,-4});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{0,2});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{2,-5,-2,-4,3});
		System.out.println(x);
	}
}

动态规划

遍历数组时计算当前最大值，不断更新
令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
当负数出现时则imax与imin进行交换再进行下一步计算
时间复杂度：O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
	public int maxProduct(int[] nums) {
		int max = Integer.MIN_VALUE, imax = 1, imin = 1;
		for(int i=0; i<nums.length; i++){
			if(nums[i] < 0){
				int tmp = imax;
				imax = imin;
				imin = tmp;
			}
			imax = Math.max(imax*nums[i], nums[i]);
			imin = Math.min(imin*nums[i], nums[i]);
			max = Math.max(max, imax);
		}
		return max;
	}
}
public class App {
	public static void main(String[] args) throws IOException {
		int x = new Solution().maxProduct(new int[]{2,3,-2,4});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{-2,0,-1});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{-2,3,-4});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{0,2});
		System.out.println(x);
		x = new Solution().maxProduct(new int[]{2,-5,-2,-4,3});
		System.out.println(x);
	}
}