global & local
The key idea is to keep 2 variable, one is global optimal point, which is the optimal solution currently. Another is the local optimal solution, which is the optimal solution util the current step. So need to make it clear how to update between the local optimal value and global optimal value.
When optimize the local global value, we will update like this : local[i+1]=Math.max(A[i], local[i]+A[i])
for the global value, we will update it like this : global[i+1]=Math(local[i+1],global[i])
Example Problem Set :
Max Sub-array
public int maxSubArray(int[] A) {
if(A==null || A.length==0)
return 0;
int global = A[0];
int local = A[0];
for(int i=1;i<A.length;i++)
{
local = Math.max(A[i],local+A[i]);
global = Math.max(local,global);
}
return global;
}
Jump Game 1
public boolean canJump(int[] A) {
if(A==null || A.length==0)
return false;
int reach = 0;
for(int i=0;i<=reach&&i<A.length;i++)
{
reach = Math.max(A[i]+i,reach);
}
if(reach<A.length-1)
return false;
return true;
}Jump Game 2
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.empty()) return 0;
int start = 0, end = 0, limit = 0;
int result = 0;
while(limit < nums.size() - 1) {
result++;
for (int j = start; j <= end; j++) {
limit = max(limit, nums[j] + j);
if (limit >= nums.size() - 1) return result;
}
start = end + 1;
end = limit;
}
return result;
}
};Let us check another 2 problem set : word break 1 & 2
Here are the solution summary :
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int len = s.size();
vector<bool> result(len+1, false);
result[0] = true;
for (int i = 0; i < len + 1; i++) {
for (int j = 0; j < i; j++) {
if (result[j] && wordDict.find(s.substr(j, i-j)) != wordDict.end()) {
result[i] = true; break;
}
}
}
return result[len];
}
};class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
map<string, vector<string>> cache;
return dfs(s, wordDict, cache);
}
vector<string> dfs(string s, unordered_set<string>& dict, map<string, vector<string>>& cache) {
if (cache.count(s)) return cache[s];
vector<string> result;
for (int i = 0; i < s.size(); i++) {
string temp = s.substr(0, i+1);
if (dict.find(temp) != dict.end()) {
if (i == s.size() - 1) {
result.push_back(temp); break;
}
vector<string> pre = dfs(s.substr(i+1), dict, cache);
for (int j = 0; j < pre.size(); j++) {
result.push_back(temp + " " + pre[j]);
}
}
}
cache[s] = result;
return result;
}
};Stock Problem Set
Best Time to Buy and Sell Stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++) {
maxPro = max(maxPro, prices[i] - minPrice);
minPrice = min(minPrice, prices[i]);
}
return maxPro;
}
};Best Time to Buy and Sell Stock II
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
int len = prices.size();
for(int i = 0; i < len - 1; i ++) {
if (prices[i + 1] > prices[i])
result += prices[i + 1] - prices[i];
}
return result;
}
};Best Time to Buy and Sell Stock III
For this problem , we need to extend it to the general k cases.
global[i][j] : 当前到达第i天可以最多进行j次交易，最好的利润是多少
local[i][j] : 当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少
local[i][j] = max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)
global[i][j] = max(local[i][j],global[i-1][j])
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int k = 2;
if (k > prices.size()/2) return solveMaxProfit(prices);
int global[k+1] = {0};
int local[k+1] = {0};
for (int i = 0; i < prices.size() - 1; i++) {
int diff = prices[i+1] - prices[i];
for (int j = k; j >= 1; j--) {
local[j] = max(global[j-1] + max(diff, 0), local[j] + diff);
global[j] = max(global[j], local[j]);
}
}
return global[k];
}
int solveMaxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] - prices[i-1] > 0) {
result += prices[i] - prices[i-1];
}
}
return result;
}
};Best Time to Buy and Sell Stock with Cooldown
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty() || prices.size() < 2) return 0;
int n = prices.size();
int buy[n] = {0}, sell[n] = {0};
buy[0] = -prices[0];
buy[1] = max(-prices[0], -prices[1]);
sell[1] = max(0, prices[1]-prices[0]);
for (int i = 2; i < n; i++) {
buy[i] = max(sell[i-2] - prices[i], buy[i-1]);
sell[i] = max(buy[i-1] + prices[i], sell[i-1]);
}
return sell[n-1];
}
};