1912 : 연속합 (Dynamic Programming) [C,C++]

규칙을 먼저 찾기 시작했다.

이중 반복문을 사용해 전 값의 + 다음 자릿 수 값을 계속 저장하여

그 중 최댓값을 찾았다.

하지만 이 문제에서 유의할 점은 입력 정수의 개수가 최대 10만개라는 것이다.

사실상 이중 반복문을 이용하면 100000 * 100000 = 10000000000번의 연산을 하게 되므로

시간을 초과하게 된다.

그래서 반복문을 한 번 사용하되 어떻게 연속된 수의 최댓값을 판별하지..하다가

조건을 세워봤다.

조건) 전 수가 음수라면 더하지 않는다.

하지만 전 수의 전 수가 엄청나게 큰 값이라면 더해야된다.

조건) 전 수보다 큰 수가 있다면 음수여도 더해야한다.

그리고

조건) 전 수가 양수라면 더해야한다.

이 조건을 맞춰 생각해보니

조건) 전 수까지의 합이 양수라면 더해야한다.

라는 최종 조건이 나왔다.

int SequentialSum::getMax()
{
 for (int i = 1; i < this->Size; i++)
 {
        if(this->DP[i-1] > 0)
            this->DP[i] += this->DP[i-1];
        else
            continue;
        if (this->Max < this->DP[i])
      this->Max = this->DP[i];
    }
    
 return this->Max;
}

*Source of the problem = https://www.acmicpc.net/problem/1912

*문제 출처 : BAEKJOON ONLINE JUDGE