최대구간 hint

- O(n^3)

#include <stdio.h>

int main()
{
    int arr[100];
    int n, i, j, k, ans, sum;
    
    scanf("%d",&n); // 데이터 개수 
    
    for( i=0 ; i < n ; i++ ) scanf("%d", &arr[i]); // 데이터 입력 
    
    ans = arr[0]; // 데이터 초기화 
    
    // 누적배열의 차를 이용해 최대값 구하기
    for( i=0 ; i < n ; i++ )
        for( j=0 ; j < i ; j++ )
        {
            sum = 0; // sum 초기화 
            for( k=j ; k < i ; k++) sum+=arr[k]; // j부터 i까지의 배열을 sum에 더해준다. 
            if( ans < sum ) ans = sum; // 최대값을 비교해준다. 
        }

    // 최대값 출력 
    printf("%d\n", ans);
}

- O(n^2)

#include <stdio.h>

int main()
{
    int sum[100]={0,}, arr[100];
    int n, i, j, ans;
    
    scanf("%d",&n); // 데이터 개수 
    
    for( i=0 ; i <  n ; i++ ) scanf("%d", &arr[i]); // 데이터 입력 
    
    for( i=0 ; i < n ; i++ ) // 누적배열 사용 
    {
        if( i==0 ) sum[i] = arr[i];
        else sum[i] = sum[i-1] + arr[i];
    }
    
    ans = arr[0]; // 데이터 초기화 
    
    // 누적배열의 차를 이용해 최대값 구하기
    for( i=0 ; i < n ; i++ )
        for( j=0 ; j < i ; j++ )
            if( ans < sum[i] - sum[j] ) ans = sum[i] - sum[j]; 

    // 최대값 출력
    printf("%d\n", ans);
}

- O(n) 으로 구현하기

- 접근 방법: dynamic programming 

- 점화식 : dy[i] --데이터 배열을 a[] 라 하는 경우 a[i] 를 구간의 끝으로 하는 경우 최대 값 
dy[i] = max ( dy[i-1] + a[i] , a[i]) 

- 답 : dy[] 중 최대값 

(a[i] 가 구간의 끝으로 두는 경우 기존 구간에 붙거나 혹은 단독으로 가는 두가지 중 최대

   
소스:
int main()
{
   int a[100],dy[100]={0},ans,i,n;

   //입력
   scanf("%d",&n); //데이터개수
   for( i = 1 ; i <= n ; i++){
      scanf("%d",&a[i]); 
   } 
   
   //처리
   for( i = 1 ; i <= n ; i++){
      dy[i] = a[i] > a[i] + dy[i-1] ? a[i] : a[i] + dy[i-1];
   }

   //최대값 찾기 
   ans = dy[1];
   for( i = 2 ; i <= n ; i++){
      if ( ans < dy[i] ) ans = dy[i];
   }

   //출력
   printf("%d\n",ans);
}