[Algorithm] Baekjoon 1912번 : 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

int arr[100001] = { 0 };
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    
    int end = 0;
    int sum = 0;
    int answer = 0x3f3f3f3f * -1;
 
    while (end < n)
    {
        sum += arr[end];
        answer = max(answer, sum);
 
        if (sum < 0)
        {
            sum = 0;
            ++end;
            continue;
        }
 
        ++end;
    }
 
    cout << answer;
 
    return 0;
}

 

프로그래머스문제 풀다가 관련 기본문제를 푼다음 풀어봐야겠단 생각에 풀어본 문제.

부분수열중 최대값을 구하는 문제인데, 기본적인 투포인터문제라 봐도 된다.

아직 안풀어봤다면 꼭 풀어보는 걸 추천한다.

 

로직은 간단하다.

매 차례마다 end에 위치한 값을 누적시키고 answer에 갱신한다.

단! 누적값이 음수라면 해당 구간은 전혀 쓸모가 없다. 

예를들어 현재 누적값이 10인데 특정인덱스값이 -9999이면? -9999값을 절대 포함시키면 안되니까 start를 -9999의 다음인덱스까지 끌어올려야 한다.

즉 그 다음인덱스부터 다시 시작하는 것이다.

 

여기서 초기 answer값을 그냥 0으로 하면 절대 안된다. 문제마다 다르겠지만, 주어지는 수열의 모든 원소값이 음수일 수 있기 때문이다. 즉, 최대값이 음수가 될 수도 있다는 거다. 

그렇기 때문에 초기 answer값은 반드시 최대의 음수값보다 더 크게 설정해줘야 한다.

그냥 0으로 해버리면 문제의 답은 -1인데 작성한 코드에서는 0을 출력해버릴 것이다.

 

==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== =

 

그냥 for문으로 i = 0부터 n까지 돌리는거랑 똑같은 코드다.

 

https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray