[AcWing] 股票買賣 II

股票買賣 II

題目

給定一個長度為 N 的數組，數組中的第 i 個數字表示一個給定股票在第 i 天的價格。

設計一個算法來計算你所能擷取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

輸入格式

第一行包含整數 N，表示數組長度。

第二行包含 N 個不大于 10000 的正整數，表示完整的數組。

輸出格式

輸出一個整數，表示最大利潤。

資料範圍

1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105

輸入樣例

6

7 1 5 3 6 4

輸出樣例

7

題解

思路

• 計算所有相鄰遞增的兩個數之差的和

#include <iostream>

using namespace std;

const int N = 1e5 + 20;
int n, a[N];

int main () {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    
    int res = 0;
    for (int i = 0; i + 1 < n; i ++) 
        if (a[i] < a[i+1])
            res += a[i+1] - a[i];
    
    cout << res;
    return 0;
}