[Lintcode]191. Maximum Product Subarray/[Leetcode]152. Maximum Product Subarray
191. Maximum Product Subarray/152. Maximum Product Subarray
- 本题难度: Medium
- Topic: Dynamic Programming
Description
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
我的代码
def maxProduct(self, nums):
# write your code here
lmax = nums[0]
lmin = nums[0]
res = nums[0]
for num in nums[1:]:
if num<0:
lmin, lmax = lmax, lmin
lmin = min(num*lmin,num)
lmax = max(num*lmax,num)
if lmax>res:
res = lmax
return res
思路
[2,3, -2, 4, -1 ,2,-3]
2, 6, -2, 4, 48 , 96, 32
2, 3, -12, -48, -4, -8, 288
第一行为连续到这一点的子数列最大值。
第二行为连续到这一点的子数列最小值。
- 时间复杂度 O(n)
1、008多对一 关联映射 --- many-to-one
2、SpringMVC运行原理浅析
3、虚拟机环境下使用java访问hbase进行表操作2
4、Hdu--1695（数论，欧拉函数，容斥原理）
5、hdu 4920 Matrix multiplication bitset优化常数