leetcode309
10993 ワード
ダイナミックプランニングを使用すると、次のコードは210のテストに合格し、最後の1つ(211番目)がタイムアウトします.説明の構想は正しいが、中には無効な計算がある.
更にネット上のACの参考の実現を提供します:
追加:
転載先:https://www.cnblogs.com/asenyang/p/9778792.html
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n==0)
{
return 0;
}
int N=5000;
int **D;
D = new int*[N];
for(int i=0;i){
D[i]=new int[N];
}
for(int i=0;i){
for(int j=i;j){
int pj=prices[j];
int pi=prices[i];
D[i][j]=pj-pi;
}
}
for(int len=1;len){
for(int i=0;i1;i++){
int j=i+len;
if(j>=n){
break;
}
int m_ij=D[i][j];
int max_k=0;
for(int k=i+1;k){
int m11 = D[i][k];
int m12=0;
if(k+2<j){
m12=D[k+2][j];
}
int m1=m11+m12;
int m21=D[k][j];
int m22=0;
if(k-2>i){
m22=D[i][k-2];
}
int m2=m21+m22;
int m=max(m1,m2);
max_k=max(max_k,m);
}
D[i][j]=max(m_ij,max_k);
}
}
return D[0][n-1];
}
};
更にネット上のACの参考の実現を提供します:
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1)
return 0;
int s0 = 0;
int s1 = -prices[0];
int s2 = INT_MIN;
for (int i = 1; i < prices.size(); i++){
int pre0 = s0;
int pre1 = s1;
int pre2 = s2;
s0 = max(pre0, pre2);
s1 = max(pre0 - prices[i], pre1);
s2 = pre1 + prices[i];
}
return max(s0, s2);
}
};
追加:
1 class Solution {
2 public:
3 int maxProfit(vector<int>& prices) {
4 int len = prices.size();
5 if(len == 0 || len == 1)
6 return 0;
7 if(len == 2)
8 return prices[1] > prices[0] ? prices[1] - prices[0] : 0;
9
10 vector<int> s0(len);
11 vector<int> s1(len);
12 vector<int> s2(len);
13 s0[2] = 0;
14 s1[2] = max(-prices[1], -prices[0]);
15 s2[2] = prices[1] - prices[0];
16 for(int i = 3; i < len; i++)
17 {
18 s0[i] = max(s0[i-1], s2[i-1]);
19 s1[i] = max(s0[i-1] - prices[i-1], s1[i-1]);
20 s2[i] = s1[i-1] + prices[i - 1];
21 }
22 return max(max(s0[len-1], s2[len-1]), s1[len-1] + prices[len-1]);
23 }
24 };
転載先:https://www.cnblogs.com/asenyang/p/9778792.html