LintCode乘积最大子序列

找出一个序列中乘积最大的连续子序列（至少包含一个数）。

样例

比如, 序列 [2,3,-2,4] 中乘积最大的子序列为 [2,3] ，其乘积为6。

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
public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
		if(null == nums || nums.length <= 0)
		{
			return 0;
		}
		
		int max = nums[0];
		int min = nums[0];
		int mostMax = max;
		
		for(int i = 1;i < nums.length;i++)
		{
			int tempMax = max;
			max = Math.max(Math.max(nums[i], tempMax * nums[i]),min * nums[i]);
			min = Math.min(Math.min(nums[i], tempMax * nums[i]),min * nums[i]);

			if(max > mostMax)
			{
				mostMax = max;
			}
		}
		return mostMax;
	}
}