↓ Skip to main content
111qqz’s blog
  1. Posts/

leetcode 152. Maximum Product Subarray (最大连续子序列乘积，dp)

·289 words·1 min
ACM DP Leetcode
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

思路：由于有正，有负，还有0.。。所以比最大子串之和要复杂一些。。。

dp[i].max表示到当前位置的最大乘积。

dp[i].min表示到当前位置的最小乘积。

dp[i].max = max{dp[i-1].maxa[i],dp[i-1].mina[i],a[i]};

dp[i].min同理

边界dp[i].max = dp[i].min = a[0]

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月14日 星期五 18时57分13秒
 4File Name :152.cpp
 5************************************************ */
 6class Solution {
 7
 8public:
 9
10    //dp
11    //dp[i]表示当前的最大乘积。
12    //用了滚动数组优化空间/
13    int maxProduct(vector<int>& nums) {
14	int siz = nums.size();
15	int mnpre,mncur,mxpre,mxcur;
16	int ret;
17	ret = mnpre = mncur = mxpre = mxcur = nums[0];
18	for ( int i = 1 ; i < siz ; i++ )
19	{
20	    mncur = min(nums[i],min(nums[i]*mnpre,nums[i]*mxpre));
21	    mxcur = max(nums[i],max(nums[i]*mnpre,nums[i]*mxpre));
22	    ret = max(ret,mxcur);
23	    mnpre = mncur;
24	    mxpre = mxcur;
25	}
26	return ret;
27
28    }
29
30};

Related

leetocde 63. Unique Paths II

·337 words·1 min
ACM DP Leetcode
Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. 1[ 2 [0,0,0], 3 [0,1,0], 4 [0,0,0] 5] The total number of unique paths is 2. 题意：从左上到右下的方案数，有些点不能走。

leetcode 64. Minimum Path Sum (二维dp)

·371 words·1 min
ACM DP Leetcode
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. 数字三角形。。。。从左上到右下问最短路径。。每次只能向下或者向右。。。 wa了一次。。。是因为边界值赋值成了0.。。求最短路径显然因为赋值成inf才对orz..果然傻了。。

leetcode 228. Summary Ranges

·412 words·1 min
ACM Leetcode
Given a sorted integer array without duplicates, return the summary of its ranges. For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"]. 题意：把连续的数连续表示 思路：模拟。注意有负数，注意有-2147483648这种数据。 本来还想着，可能是leetcode加数据的审核机制太松，导致被人加了奇怪的数据。。。

leetcode 209. Minimum Size Subarray Sum (尺取法)

·248 words·1 min
ACM 双指针 Leetcode
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead. For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint 思路：尺取即可。。好久没写，竟然调了半天。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月13日 星期四 20时48分00秒 4File Name :209.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 int ruler(vector<int>nums,int tar,int n) 11 { 12 int head = 0; 13 int tail = 0; 14 int sum = 0 ; 15 int res = 0x3f3f3f3f; 16 while (tail<n&&head<=tail) 17 { 18 sum = sum + nums[tail]; 19 if (sum>=tar) 20 { 21 res = min(res,tail-head+1); 22 while (sum>=tar&&head<tail) 23 { 24 sum-=nums[head]; 25 head++; 26 } 27 if (sum>=tar) 28 { 29 res = min(res,tail-head+1); 30 } 31 else 32 { 33 head--; 34 sum+=nums[head]; 35 res = min(res,tail-head+1); 36 } 37 } 38 39 40 41 tail++; 42 } 43 return res==0x3f3f3f3f?0:res; 44 } 45 46 47 int minSubArrayLen(int s, vector<int>& nums) { 48 int n = nums.size(); 49 int res = ruler(nums,s,n); 50 return res; 51 52 53 } 54 55};