Say you have an array for which the ith element
is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock
before you buy again).
第一反应还是分割范围的DP，即 f( i,j ) = max ( f (i,k) +f(k,j) )，枚举k这样子的，但是明显复杂度是o( n3)的，估计这个题意不是那样的，管他的呢，先写了再说锻炼下DP。
为了方便转移，把 f ( i, len)定义成以i开头的长为len的这一子序列的最大收益，所以枚举长度即可。
注意我们的计算是从len的长度从小到大进行的，所以为了提高读取数组的效率，我们将二维数组的第一位设定为长度len，第二维是起始点i。
代码如下：
#include<iostream>
#include<vector>
using namespace std;
#define vi vector<int>
#define vvi vector<vi >
class Solution {
public:
int maxProfit(vi& price)
{
int n=price.size();
if (n<=1)
return 0;
vvi dp(n+1,vi(n,0));
int i,k,len,end;
for(i=0;i<n-1;i++)
dp[2][i]=max(0,price[i+1]-price[i]);
for(len=3;len<=n;len++)
{
end=n-len;
for(i=0;i<=end;i++)
{
for(k=1;k<len;k++)
{
dp[len][i]=max(dp[len][i],dp[k][i]+dp[len-k][i+k]);
}
dp[len][i]=max(dp[len][i],price[i+len-1]-price[i]);
}
}
return dp[n][0];
}
};
int main()
{
int n;
while((cin>>n)&&n!=0)
{
vi price(n,0);
for(int i=0;i<n;i++)
cin>>price[i];
Solution so;
int ans=so.maxProfit(price);
cout << ans <<endl;
}
}
试着提交了下，小数据4ms过（长度放第二维的话要8ms），大数据超时~ 果然~ 哈哈
然后想了下有没有简单的方法，试想序列为 1,2,3,4的时候，我们从后往前看，最后一天得不到收益，记录可卖最高价high=4,倒数第二天的时候，价格为3，小于可卖价，所以得到4-3=1的收益，然后现在可卖价格变为3（因为同时只能有一次交易，不能重叠嘛），再向前一天看，价格为2，小于可卖价，得到1的收益，可卖价格又变为2。。。。最后得到收益为3.
从例子的1，2，3，4来看，收益可以来自：1的时候买，4的时候出；或者，1的时候买，2的时候出，2的时候又买，3的时候出。。。即整体和分段的最后收益是一样的。所以可卖的时候我们立即就卖了，对最后的结果是一样的。
#define vi vector<int>
#define vvi vector<vi >
class Solution {
public:
int maxProfit(vi& price)
{
int n=price.size();
if (n<=1)
return 0;
int ans=0;
int high=price[n-1];
for(int i=n-1;i>=0;i--)
{
if ( price[i]<high)
ans+= high-price[i];
high=price[i];
}
return ans;
}
};