I
第一问就是个水DP，不要理解错题意，就是很简单的题目。
II
第二问是个简单的贪心策略：既然允许任意买进抛出，但是必须先抛出才能再买进，那么就是在每个时间点，先抛出再买进等价于无操作。也就是说，相当于还是只能买一只股票，但是可以重复买进抛出它。这样的话，贪心策略就出来了：就像真正股民那样，涨的时候买入，跌之前抛出即可。
III
第三问就要涉及到稍微复杂一些的DP思想了。这题的题意是说，最多允许买卖两次，并且还是先卖出后才能再买入。也就是说，我们可以在整个过程中先后买入卖出两次，目的是使得总收入最大。显然，我们将股价序列处理一下，每次用后一个值减去前一个值，得到一个新的差值序列即股价变化，这样问题就可以转换为：求在这个差值序列中不相交的两个连续子序列，使得其和最大。
此时的这个问题实际上就是HDU 1024的特例，直接套用那里的DP思路即可，由此也体现出这个DP的重要性！但是需要注意一个边界情况的处理：如果新序列中只有一个正值或者没有正值，则应返回这个唯一正数或零。原因是显然的：如果只有一个正数，就没必要强行找出两段子序列，这样反而会使得总和变小。
IV
第四问就是彻底在考察HDU 1024的算法了，只不过我们需要注意一个特殊输入：如果k远大于prices.size()，则说明我们可以任意买卖股票，此时我们只要选取所有能盈利的方案，求和即可。
HDU 1024
下面讲一下HDU 1024，这个题目的题意是，给出一个长度为n的序列，要求将其切分为m个不相交的连续子序列，使得其和最大。可以看出，这道题目是第三问的进一步推广，它的思路则非常巧妙，用到了两个一维数组进行递推。
首先要明确一点，尽管这个问题相对复杂，但是单单对于每一个元素，还是只有两种基本状态：被选取到m段中的一段里，或者根本没有被选取。因此我们定义两个状态f[i][j]和g[i][j]，其中i、j表示将前j个元素分成i部分。f[i][j]表示一定取第j个元素时的最大值，g[i][j]表示不一定取第j个元素时的最大值。所以对于f[i][j]，就有状态转移方程：
其中A为数组。上式所表示的意思是，如果分成i段并保证取第j个元素还要得到最大值，那么可以有两种策略，一种是将前j-1个元素分成i段并保证取第j-1个元素，这样就可以把第j个元素接到第j-1个后面；另一种则是将前j-1个元素分成i-1段，这时可以不要求一定取第j-1个元素，因为第j个元素可以单独拿出来自成一段。
另一方面，对于数组g[i][j]，基于类似的思路，有：
它所表示的意思是，将前j个元素分成i段，如果取第j个元素的话就是f[i][j]；如果不取的话就是将前j-1个元素分成i段，由于不要求取第j个元素所以是g[i][j-1]而不是f。
有了这两个状态转移，接下来用滚动数组递推即可，注意是逆序，因为要保留上一层的值没有被更新。初始状态下有j=0，显然不存在任何合法分割方式，除非分成零段，因此边界值初始化为负无穷。
代码
class Solution {
public:
static const int MAX = 100010;
int f[MAX], g[MAX];
int maxProfit(vector<int> &prices) {
if ( prices.size() < 2 ) return 0;
vector<int> nums;
int num_positive = 0, pos_val = 0;
for ( int i = 1; i < prices.size(); i++ ) {
int val = prices[i] - prices[i - 1];
if ( val > 0 ) {
num_positive++;
pos_val = val;
}
nums.push_back(val);
}
if ( num_positive <= 1 ) return pos_val;
return dp(nums.size(), 2, nums);
}
int dp( int n, int m, vector<int> & data ) {
for ( int i = 1; i <= m; ++i )
f[i] = g[i] = -100000000;
for ( int j = 1; j <= n; ++j )
for ( int i = m; i >= 1; --i ) {
f[i] = max( f[i], g[i-1] ) + data[j - 1];
g[i] = max( g[i], f[i] );
}
return g[m];
}
};