题解 | #买卖股票的最好时机(二)#

动态规划 dp[N][2]: dp[i][0]表示第i天不持有股票的最大收益，同理，dp[i][1] 表示第i天持有股票的最大收益。

分析：
dp[i][0]，第i天不持有股票（卖出股票），那这个状态可以来自两方面：1）来自dp[i-1][0]，前一天不持有股票，今天也不持有股票，最大收益不会变化；2）来自dp[i-1][1]+p[i]，前一天持有股票，今天不持了（卖了），买股票的时候是负收益，花钱了，所以现在卖了股票是加上今天的价格p[i]。综上，有 dp[i][0] = max(dp[i-1][0], dp[i-1][1]+p[i])。

dp[i][1]，第i天持有股票，本身包含两种状态：1）本来就持有股票，就是说dp[i-1][1]，继续再持有一天；2）本来没有股票，今天买了股票，就是dp[i-1][0]-p[i]，前一天没持有股票，今天买了今天价格的股票，就得让整个最大收益减去今天买的股票的价格

#include <iostream>
using namespace std;
const int N = 1e5+10;
int p[N];
int n;
int dp[N][2];  //dp[i][0]代表第i天没有持有股票的最大收益
int main() {
    scanf("%d", &n);
    for(int i = 1; i <=n; i++)
    {
        scanf("%d", &p[i]);
    }
    dp[1][1] = -p[1];  // 第一天持有股票，就是买了这天的股票，总收益= -股票价格
    dp[1][0] = 0;   // 第一天没持有股票，没有收益和损失=0
    for(int i = 2; i<=n;i++)
    {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+p[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-p[i]);
    }
    printf("%d",max(dp[n][1],dp[n][0]));

    return 0;
}
// 64 位输出请用 printf("%lld")