[BOJ-1912]연속합

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

이 문제는 

수열이 주어질 때 연속한 수를 선택하여 연속합을 구하는 문제임.

10 -4 3 1 5 6 -35 12 21 -1

이 입력으로 주어지면 12 + 21 이 33이므로 가장 큰 연속합이 됨.

[입력]

n

a1 a2... an-1 an 

수열의 갯수 n이 주어지고

a1 a2 ... an-1 an 이 주어진다.

[출력]

수열 중 가장 큰 연속합을 구한다.

동적계획법으로 구할 수 있다. 출력 값을 ans 

그리고 ans 보다 큰 값이 나오면 ans의 값을 갱신한다. 

(1) input[i] : i번째 수 

(2) memo[i] : i번째 까지 연속합 중 가장 큰 연속합

(3) memo[i-1] + input[i] : i-1번째 연속합 중 가장 큰 연속합 이며, i번째 수를 택한 수 

(3) 에서 이 수가 0보다 작은 경우 if( (3) < 0 ) 

이후 값을 더하더라도 음수의 값을 누적하여 가지고 있으므로 더하여도 최대 연속합이 될 수 없다.

그러기 때문에 if( (3) >= 0 ) 인 값만이 연속합이 될 수 있다. 

위 조건을 만족할 때만 memo[i]를 갱신한다. 

그리고 ans 보다 값이 클 경우 ans을 갱신한다. 

위 과정을 반복하면 연속합의 최대값을 구할 수 있다. 

9달전에 왜 이렇게 밖에 생각 못했을까 싶은데 코드는 추가함.

#include<cstdio>
 
int main(){
    int input, n;
    int max, tmpMaxSum, sum;
    max = -1000;
    tmpMaxSum = 0;
    sum = 0;
    scanf("%d",&n);
    
    while(n--){
        scanf("%d",&input);
        if(max<input){
            max = input;
        }
        
        sum +=input;
        tmpMaxSum += input;
        
        
            if(input < 0){
                sum = 0;
            }
            else if(max < sum){
                max = sum;
            }
        
        
            if(tmpMaxSum <= 0){
                tmpMaxSum = 0;
            }
            else if(max < tmpMaxSum){
                max = tmpMaxSum;
            }
                
    }
    printf("%d\n",max);
        
    return 0;
    
}

#include<cstdio>
 
const int MAX = 111111;
int input[MAX];
int memo[MAX];
// memo[i] : i번째 수까지 연속합을 저장, 연속합이 음수가 될 경우 0
 
int main() {
   int ans = -1111;
   int n; scanf("%d", &n);
   for (int i = 1; i <= n; i++) {
      scanf("%d", &input[i]);
      ans = (ans > input[i]) ? ans : input[i];
      if (memo[i - 1] + input[i] >= 0) { 
         // i-1 번째까지 더해진 값 최대값 + i 번째 입력이 양수,0 이라면
         // 이후에 더해질 값이 존재할 때 최대값이 될 수 있는 가능성이 있다.
         memo[i] += memo[i - 1] + input[i];
         ans = (ans > memo[i]) ? ans : memo[i];
      }
      //else { 
      // 하지만 i-1 번째까지 더해진 값 최대값 + i 번째 입력이 음수라면 
      // 이후 수가 더해져도 +음수를 더해진 값이므로 최대값이 될 수 없다.
      //   memo[i] = 0;
      //}
   }
   printf("%d\n", ans);
   return 0;
}