[C++] 백준 25644 최대 상승 – 그리디 + 누적 최소값

📌 문제 개요

🔗 백준 25644번: 최대상승

문제 설명
주가가 N일간 어떻게 변할지 알 때,
주식 1주를 적절한 날에 사고 팔아 최대 이득을 구하기

• 조건
  • 날짜 수 N (1 ≤ N ≤ 200,000)
  • 각 날의 주가 a₁ ~ aₙ (1 ≤ aᵢ ≤ 10⁹)
• 목표
  • 한 번만 사고, 한 번만 팔때 최대 이익 계산

💡 문제 분석

• 단 한 번의 매수/매도 → 이전 최솟값 대비 최대 이익
• 두 수 i < j를 골라 a[j] - a[i]를 최대화
• i < j 조건 때문에 순서를 유지해야 함.
• a[i] > a[j]라면 이득 = 0

🔑 아이디어 도출

• 브루트포스 O(N²) ❌ → 시간초과 발생
• 한 번의 순회(O(N))로 해결 가능

🚫 잘못된 접근 – 완전탐색 ❌

for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        maxProfit = max(maxProfit, a[j] - a[i]);

• 모든 쌍 (i, j)에 대해 이익 계산 → O(N²)
• 최대 4 × 10¹⁰ 연산 → 시간 초과 확정

---

🧩 풀이 전략

핵심 아이디어

현재 가격	이전까지 최솟값	현재 이익	최대 이익
7	7	0	0
1	1 (갱신)	0	0
4	1	3	3
6	1	5	5

• 이전까지 가장 싸게 살 수 있었던 날을 계속 기억.
• 매 순간 현재 가격 - 최솟값 계산해서 이득 갱신

✅ 그리디 + 누적 최소값

조건	내용
매일 최솟값 갱신	min_price = min(min_price, aᵢ)
이익 계산	profit = aᵢ - min_price
최대 이익 갱신	max_profit = max(max_profit, profit)

💻 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int min_price;
    long long max_profit = 0;
    cin >> min_price;

    for (int i = 1; i < n; i++) {
        int price;
        cin >> price;

        max_profit = max(max_profit, 1LL * price - min_price);
        min_price = min(min_price, price);
    }

    cout << max_profit << "\n";
    return 0;
}

---

⏱️ 시간/공간 복잡도 분석

• 시간 복잡도 O(N) → 1회 순회
• 공간 복잡도 O(1) → 상수 공간 사용

---

✨ 핵심 포인트 요약

• 매일 최솟값 갱신 + 이익 계산 → 최대값 추적
• 브루트포스 ❌ → 누적 최소값으로 최적화
• O(N)으로 시간초과 없이 해결 가능
• 비슷한 문제:
  • 백준 11004 K번째 수
  • 백준 1285 동전 뒤집기

✨ 다음 추천 문제:

• 백준 10211 Maximum Subarray
• 백준 1912 연속합 (Kadane’s Algorithm)

📝 추가 팁 – 확장 문제

이 방식은 주식 문제뿐만 아니라,
최대 상승 폭, 최대 이익, 최대 증가 구간 문제에서 그리디 + 누적 최솟값/최댓값 으로 자주 활용됨