연속합 (DP)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#define N 100001

long long dp[N], MAX= -1000, test, SUM;

long long arr[N];

void sum(int a)

{

for (int i = 1; i <= a; i++)

{

SUM += arr[i];

if (MAX < SUM)

MAX = SUM;

if (SUM <= 0)

SUM = 0;

}

}

int main()

{

scanf("%lld", &test);

for (int i = 1; i <= test; i++)

scanf("%lld", &arr[i]);

sum(test);

printf("%lld", MAX);

return 0;

}

내가 푼 방법은

10부터 -1까지 쭈루루룩 더하는데 

더하면서 합이 양수면 계속 돌진 음수면 합을 0으로 초기화후 다시 돌진 

예를 들면  10 + (-4) = 6 이다 그러므로 계속 돌진 !    ->  6 + 3 = 9 이므로 계속 돌진한다..  이렇게 쭈루룩  6 까지 계속 돌진하면 합은 21이다

근데 큰일났다.    -35라는 거대한 음수가 튀어나왔다.    더해보니  21 + (-35) =  -14 라는 음수가 나온것이다.  음수는 나쁜것이니까 버려야한다.

그러므로 0이되었고 여기서 중요한게 21이라는 것을 MAX라는 변수에 넣어놔야함 .

다시 12부터 쭈루루룩 더한다.    12 + 21 = 33(최대값)이 나오고 조건문을 통해 MAX에는 33이 대입된다.   그다음  33 + (-1)을 하고 종료된다.

여기서 주의해야하는게 MAX에다 0을 넣으면안됨.

왜냐하면 입력때 모든 수가 음수일 수가 있다.  

요로코롬  -3 -5 -2 -1 -6  이렇게 다섯가지의 숫자가 입력될수 있는데 여기서 출력은  -1이 출력되야하는데,   MAX 에 0을 넣어놨다면  마지막 출력도 0이 나와버림.   그래서 시작할때  입력할수있는 가장 적은 수인 -1000을 미리 넣어놨다.