다이나믹 프로그래밍을 공부하다보면 나오는 부분합 문제이다! 확률 보고 쫄았는데 생각보다 할만하다 ㅎㅎ

문제

  • 첫째 줄에 정수의 갯수가 주어지고 그 다음줄부터 정수의 갯수만큼 입력이 주어진다.
  • 이 중에 한 개 이상을 연속으로 선택하여 만들 수 있는 합 중에서 최대값을 구하면 된다.

입력

  • 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

예제 입력
10
10 -4 3 1 5 6 -35 12 21 -1
예제 출력
33

접근

  • 다이나믹 프로그래밍을 어떻게 사용할까?
  • 최대값을 만들기 위한 조건은 무엇일까?

내가 생각한 풀이

  • Index를 지날 때 마다 연속된 숫자들의 합을 구해주고 만약 음수가 아니라면 계속 더한다.
    • 만약 음수가 아니라면 그 다음 수를 더할 경우 값이 증가할 것임.
  • 만약 음수가 된다면 해당 Index에 맞는 입력값으로 값을 초기화 시켜준다.
  • 더할 때 마다 최대값을 갱신해준다.

코드

//그 전까지의 합이 음수가 될 경우 그 다음 값을 더하더라도 절대 최대값이 될 수 없다는 생각을 했다.
//따라서 그 전까지의 합이 양수라면 계속해서 더해주고 그렇지 않다면 해당 index의 배열 값으로 초기화 시켜준다.
#include<iostream>
using namespace std;

int main(void){
  int c, r, n[10002], dp[10002];
  cin>>c;
  for(int i = 1 ;i<=c;i++)
    cin>>n[i];
  dp[1] = n[1];
  if(c == 1){cout<<n[1]; return 0;} //1과 2일때는 어짜피 경우의 수가 저것 밖에 없음.
  if(c == 2){cout<<max(max(n[1]+n[2],n[2]),n[1]); return 0;}
  r = dp[1];
  for(int i = 2 ;i<=c;i++){
    if(dp[i-1]>0) dp[i] = dp[i-1] + n[i]; //그 전까지의 합이 양수이면 더하기 연산
    else dp[i] = n[i]; // 만약 그 전의 값이 음수라면 배열의 값으로 초기화 시켜줌.
    if(dp[i]>r) r = dp[i]; //최대값 비교
  }
  cout<<r;
  return 0;
}

코드를 돌렸을 때 dp행렬을 출력해보면 다음과 같다.

10
10 -4 3 1 5 6 -35 12 21 -1
10 6 9 10 15 21 -14 12 33 32
답 : 33