[C] 1912: 연속합

이 문제도 전형적으로 dp[]라는 배열을 선언하여 각 순간마다 가장 이득인 경우를 배열에 넣어준다.

 

코드 설명에도 나와있지만 부분합이 0보다 작아지게 된다면 다시 시작하는게 이득이고

0보다 크다면 계속 이어나가는게 이득이다. 하지만 이때도 부분합이 여러개 생길 수 있는데 이 부분합중에

최대인 것을 저장하기 위해 max라는 변수를  이용해야한다.

 

이 문제를 풀때 자꾸 54%에서 실패가 났는데

알고보니 arr[]의 값이 0일때 max가 되는지 비교를 안해줘서 나타나는 오류였다.

더 치밀하게 비교하고 계획하는 연습을 해야겠다

전형적인 문제라 계획을 짜는데는 큰 시간이 들지 않았고 

dp배열과 arr배열을 헷갈리지 않고 정확하게 쓰는 연습을 조금 더 해야할 것 같다. 

 

또한 전에 정리해놓기는 했지만 최대값,최솟값과 관련된 문제가 많아

나중에 이런 문제를 만났을 때 DP를 떠올리는 연습을 해야겠다.

 

아래는 소스코드다!

 

#include <stdio.h>

int arr[100002];
int dp[100002];

  int main(void)
  {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
      {
        scanf("%d",&arr[i]);
      }
  dp[0]=arr[0];
    int max=dp[0];
    for(int j=1;j<n;j++)
      {
        if(dp[j-1]>0) //지금까지의 합이 0보다 크면 계속 더하는게 이득임
        {
          if(arr[j]<0 && dp[j-1]>max) //현재의 수가 음수이면 그전까지가 최대일 수도 있음
            max=dp[j-1];
          dp[j]=dp[j-1]+arr[j];  //dp[j]입장에서는 arr[j]가 음수라면 dp[j-1]이 0보다 클때 더하는게 무조건 이득임        
        }
        else //지금까지의 합이 0보다 작으면 새로 부분합을 시작하는게 이득
        {
          
          dp[j]=arr[j];
          if(dp[j]>max) //dp[j]가 0이고 이때 이게 최대일 수 있음
            max=dp[j];
        }
        
      }
   /*for(int i=0;i<n;i++)
      {
        printf("%d ",dp[i]);
      }
    printf("\nmax:%d arr:%d\n",max,dp[n-1]);*/
   
    max=max>dp[n-1]?max:dp[n-1]; //맨 마지막에는 max 비교를 못해줫음 
    printf("%d",max);
  }