CSES 2. Maximum Subarray Sum (1643)

출처: https://cses.fi/problemset/task/1643

---

문제 설명

Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

입력 

The first input line has an integer n: the size of the array.

The second line has n integers x_1, x_2,…,x_n: the array values.

출력 

Print one integer: the maximum subarray sum.

입력 예 

8
-1 3 -2 5 3 -5 2 2

출력 예

9

제약조건

• 1 <= n <= 2x10^5
• −10^9 <= x_i <= 10^9

---

문제 풀이

배열에 값을 읽어들이면서, 부분합(1~ k) 을 기록한다.

새로운 배열값과 부분합을 비교해서 최대값을 기록한다.

프로그램 내용

...
    long num_array[nNum] = {0};
    long best = -1000000007, sum = -1000000007;

    for (int idx = 0; idx < nNum; idx++)
        cin >> num_array[idx];
        sum = max(num_array[idx],sum+num_array[idx]);
        best = max(best,sum);

...

 

Sorting and Searching ( link )