AcWing 1058. 股票买卖 V
原题链接
中等
作者:
leimingze
,
2022-02-22 14:29:02
,
所有人可见
,
阅读 106
//author:leimingze
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define _ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define LL long long
#define ULL unsigned unsigned
#define PII pair<int,int>
#define MOD 1e9+7
#define INF 0x3f3f3f3f
#define eps 1e-8
const double PI = acos(-1.0);
const int dx4[4] = { 0,-1,0,1 };
const int dy4[4] = { -1,0,1,0 };
//#pragma warning(disable:4786)//使命名长度不受限制
//#pragma comment(linker, "/STACK:102400000,102400000")//手工开栈
int qmi(int a, int k, int p) { int res = 1 % p; while (k) { if (k & 1)res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; }return res; }
template <typename T> void inline read(T& x)
{
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
//不开long long 见祖宗,递归剪枝
const int N = 1e5 + 10;
int w[N];
int f[N][3];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> w[i];
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++)
{
if (i == 1)
{
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][0] - w[i];
}
else
{
f[i][0] = max(f[i - 1][0], f[i - 1][2]);
f[i][1] = max(f[i - 1][0] - w[i], f[i - 1][1]);
// f[i][2] = (f[i][2], f[i - 1][1] + w[i]);可以替换下一行
f[i][2]=f[i-1][1] + w[i];
}
}
int res = 0;
for (int i = 0; i <= 2; i++)res = max(res, f[n][i]);
cout << res << endl;
return 0;
}