14279: 【原4279】Stock Manager

题目

题目描述

author: Jarvis 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4279

Description

Say you have an array of stock prices, in which the i-th element is the price on day i.

Design a strategy of stock transactions to gain the maximum profit. A complete transaction includes buying and selling one share of the stock. The number of transactions in unlimited.

Note that you must sell the stock you hold before you buy again.

Input Format

Two lines. The first line is an integer, which is the number of prices (days). The second line is an array, which contains the stock prices.

Output Format

One integer. The maximum profit.

Sample Input

6
7 1 5 3 6 4

Sample Output

7

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/cs222quiz_2019.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[1000005];
int f[1000005] = {0}, g[1000005] = {0};
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
}
void solve(){
    int maxi = -a[1];
    for (int i = 2; i <= n; ++i){
        f[i] = a[i] + maxi;
        g[i] = max(g[i - 1], f[i]);
        maxi = max(maxi, g[i - 1] - a[i]);
    }
    printf("%d\n", g[n]);
}
int main(){
    init();
    solve();
    return 0;
}