ข้อสอบท้ายค่าย 2 ปีการศึกษา 2566 ศูนย์ สอวน. มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ข้อ Stock

Author: Nagorn Phongphasura

Problem

สรุปโจทย์

มีวันอยู่ทั้งหมด \(N\) วัน แต่ละวัน หุ้นจะมีราคา \(P_i\) บาท ซีเคสามารถซื้อขายหุ้นได้หลายรอบ แต่ใน 1 วันจะซื้อหรือขายได้เพียงรอบเดียว(หรือไม่ซื้อขายหุ้นเลยก้ได้)

สิ่งที่ต้องทำ

หากำไรที่มากที่สุดจากการซื้อขายหุ้น

Constraints

\(2 \leq N \leq 10^5\)
\(0 \leq P_1,P_2,...,P_N \leq 10^9\)

Prerequisites

Math

Solution

Claim: ผลรวมของกำไรที่มากที่สุดที่เป็นไปได้ มีค่าเท่ากับ

\[ \sum_{i = 1}^{N - 1} \max(0, p_{i + 1} - p_i) \]

Proof: สมมติให้ลำดับการซื้อขายหุ้นที่จะทำให้ได้กำไรมากที่สุด คือการซื้อที่ตำแหน่ง \(\{i_1, i_2, ..., i_k\}\) และขายที่ตำแหน่ง \(\{j_1, j_2, ..., j_k\}\)

สำหรับแต่ละรอบการซื้อขาย \( (i_m, j_m) \) กำไรของรอบนั้นจะเป็น

\[ p_{j_m} - p_{i_m} = (p_{i_m+1}-p_{i_m}) + (p_{i_m+2}-p_{i_m+1}) + \dots + (p_{j_m}-p_{j_m-1}) \]

ซึ่งเท่ากับ ผลรวมของราคาที่เพิ่มขึ้น ในทุกๆคู่วันที่อยู่ติดกัน

แต่ว่า ถ้าในวันไหนราคาลดลง การซื้อขายในวันนั้นจะทำให้ได้กำไร \(\leq 0\) เราจึงไม่ควรขายหุ้นในวันนั้น
ดังนั้น กำไรที่สูงที่สุดที่เป็นไปได้ คือการรวมผลต่างของราคาในวันที่ราคาเพิ่มขึ้น (\(p_{i+1} - p_i > 0\))

จะได้ สูตรหากำไรที่สูงที่สุด คือ

\[ \sum_{i = 1}^{N - 1} \max(0, p_{i + 1} - p_i) \]

ดังนั้น วิธีทำโจทย์ข้อนี้ คือ Loop ตั้งแต่ 1 ถึง \(N - 1\) แล้วในแต่ละรอบ เพิ่มค่าคำตอบไปด้วย \(max(0, p_{i + 1} - p_i)\)

Code:

c2_kmutt_66_stock.cpp

#include <bits/stdc++.h>
#define int long long

using namespace std;

int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);

    // input
    int n;
    cin >> n;
    vector <int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];

    int ans = 0; // เก็บผลรวมคำตอบ

    // Loop เพื่อคำนวณ
    for (int i = 1; i < n; i++) {
        ans += max(0ll, p[i + 1] - p[i]);
    }

    // Output
    cout << ans << "\n";
    return 0;
}

Total Time Complexity

\(O(N)\)