프로그래머 면접 100문제---3.하위 그룹의 최대 합을 구합니다.

프로그래머 면접 100문제---3.하위 그룹의 최대 합을 구합니다.
문제 설명:
성형수조를 입력하면 수조에 양수도 있고 음수도 있다.수조에 연속된 하나 이상의 정수가 하나의 자수조를 구성하고, 각 자수조마다 하나의 합이 있다.모든 하위 그룹의 최대 값을 구하십시오.요구 시간의 복잡도는 O(n)이다.
예를 들어 입력한 수조는 1,-2,3,10,-4,7,2,-5이고 가장 큰 수조는 3,10,-4,7,2이기 때문에 이 수조의 출력은 18이다.
문제 분석:
해법 1, 직접법,sum[i.j]을 설정하여 수조 중 i에서 j 사이의 모든 숫자의 합을 계산하고 모든sum를 계산하여 그 중에서 가장 큰 것을 구한다. 시간 복잡도는 O(N^2)이다.

int max_sum1(int a[],int n)
{
     if(!a || n < 0)
          exit(1);

     int max = -1;
     int i,j,sum;
     for(i = 0; i < n; i++)
     {
          sum = 0;
          for(j = i; j < n; j++)
          {
                sum += a[j];
                if(sum > max)
                   max = sum;
           }
 
      }
      return max;
}

이 해법은 약간 폭력적이기 때문에 성능이 비교적 낮다.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
해법 2:
/* DP 문제: (a[k]....a[n-1])의 가장 큰 세그먼트와 a[k]를 이미 알고 (a[k]....a[n-1])에 A[k]를 포함하는 가장 큰 세그먼트와 Start[k]를 계산했다면 All[k-1]=max{a[k-1], a[k-1]+Start[k], a[k],*//

int max_sum2(int a[], int n)
{
    int i;
    int nAll,nStart;
    if(!a || n < 0)
        exit(1);
    
    nAll = a[n-1];
    nStart = a[n-1];

    for(i = n - 2; i >= 0; i--)
    {
        nStart = max(a[i], a[i] + nStart);
        nAll = max(nAll,nStart);
    }

    return nAll;
}