题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int N;

/*
必须在再次购买前出售掉之前的股票
0表示未持股 1表示持股
f[i,j]表示股票在第i个价位上是买入还是卖出,j=1/0,的最大利润
递归公式：(先画出状态转换图)
f[i][0] = max(f[i - 1][1] + nums[i] , f[i - 1][0]); 由i-1的持股加上i的股价便是收益,和,i-1的未持股 取最大值
f[i][1] = max(f[i - 1][0] - nums[i] , f[i - 1][1]);
*/
int main(){
    cin >> N;
    vector<int> nums(N);
    vector<vector<int>> f(N , vector<int>(2));
    for(int i = 0 ; i < N ; i++){
        cin >> nums[i];
    }

    //初始化：
    f[0][0] = 0 , f[0][1] = -nums[0];

    for(int i = 1 ; i < N ; i++){
        f[i][0] = max(f[i - 1][1] + nums[i] , f[i - 1][0]);
        f[i][1] = max(f[i - 1][0] - nums[i] , f[i - 1][1]);
    }
    cout << f[N-1][0] << endl;

}