프로그램 경연 공략을위한 알고리즘 및 데이터 구조 ALDS_1_1_D : Maximum Profit p46

프로그래밍 경연 공략을 위한 알고리즘과 데이터 구조 p46 Maximum Profit J는 최대값을 찾으면 좋으니까 n회 탐색이 된다. J에서 왼쪽의 최소값을 기억해 두면 된다. <<이 발상을 할 수 있는 것이 열쇠. 매번 최소값을 찾아가지 않아도 된다. 계산량은 이것으로 O(n)이 된다. 이것은 특별한 번병 문제일까? SublimeText3에서 C++를 부담없이 실행하는 환경을 만든다. - Qiita
sablime txt3에서 실행하면 입력이 불가능하기 때문에 수동 입력 부분을 주석 처리했습니다.

#include "iostream"
// #include "algorithm"
using namespace std;
// static const int MAX = 200000;

int main()
{
    /* 手動入力
    int R[MAX],n;

    cin >> n;
    for (int i = 0; i < i < n; ++i) {
        cin >> R[i];
    }
    */
    const int n = 6;
    int R[n]={5,3,1,3,4,3};

    int maxv = R[1] - R[0];
    int minv = R[0];

    for (int j = 1; j < n; ++j) {
        maxv = max(maxv, R[j] - minv);
        minv = min(minv, R[j]);
    }

    cout << maxv << endl;

    return 0;
}

입력
출력


6개
이익 3

R[0] = 5

R[1] = 3

R[2] = 1

R[3] = 3

R[4] = 4

R[5] = 3



maxv R[1]-R[0] = -2(또는 -10^9 이하)
minv R[0] = 5 R[j]의 최소값

R [j]보다 왼쪽의 최소값을 기억합니다.
그것을 R[j]의 최고치에서 빼면 대답이 나온다.

알고리즘
J를 1에서 n-1까지(=전부 조사한다)
maxv maxv와 R[j]-minv의 큰 쪽
minv minv와 R[j] 중 작은 사람


j
R
maxv
minv



R[0] = 5
-2
5

1
R[1] = 3
-2
3

2
R[2] = 1
-2
1

3
R[3] = 3
2
1

4
R[4] = 4
3
1

5
R[5] = 3
3
1


참고도서
프로그래밍 경연 공략을 위한 알고리즘과 데이터 구조 곧 이해할 수 없었기 때문에 메모. 아직도 이중 루프가 되면, 어느 수치가 어떻게 움직이는지 순간에 이해할 수 없다, 이것은 횟수를 거듭해 문제를 풀 수밖에 없다··orz.