算法1

(动态规划)

• dp[i][0] 表示到第 i 天结束手里没有股票的最大利润
• dp[i][1] 表示到第 i 天结束手里握有股票的最大利润.

转移：
第 i 天结束没有股票 ：昨天就没有股票，或者昨天还有股票，今天刚抛出

  dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + a[i]); 

第 i 天结束握有股票 ：昨天就有股票，或者昨天还没有股票，今天刚买进

  dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - a[i]);

故最后的答案就是max(dp[n][0], dp[n][1]), 不过到这一天时股票卖出了肯定比握在手里利润大

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], dp[N][2];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    dp[1][0] = 0, dp[1][1] = -a[1];

    for(int i = 2; i <= n; ++ i){
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + a[i]); 
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - a[i]);
    }
    cout << dp[n][0] << endl;    

    return 0;
}

算法2

(优化)

其实 dp 数组 可以优化成两个变量 dp0： 表示dp[i][0] ; dp1： 表示dp[i][1]。
而保存每天股票价格的数组 a 也可以去掉，边读入每天的价格，边进行状态转移

C++ 代码

#include <iostream>
using namespace std;


int main()
{
    int n;
    cin >> n;

    int dp0 = 0, dp1 = 0;

    cin >> dp1;
    dp1 = - dp1; //用第一天的股票价格初始化dp1

    for(int i = 2; i <= n; ++ i) {
        int cur; //从第二天开始计算
        scanf("%d", &cur);
        int tmp = dp0; //先保存 dp0 的值
        dp0 = max(dp0, dp1 + cur);
        dp1 = max(dp1, tmp - cur);
    }

    cout << dp0 << endl;    

    return 0;
}