수다닷컴

#include stdio.h
long max(long, long);
long MaxSubseqSum(int A[], unsigned Left, unsigned Right);

int main(void)
{
long num, i, s_max, seq[100000];
FILE *in, *out;

in = fopen(input.txt,r);
out = fopen(output.txt, w);

fscanf(in, %d, &num);

for(i=0; inum; i++)
fscanf(in, %d, &seq[i]);

s_max = MaxSubseqSum(seq, 0, num-1);
fprintf(out, %d\n, s_max);
fclose(in);
fclose(out);
return 0;
}

long MaxSubseqSum(int A[], unsigned Left, unsigned Right)
{
int Center, i;
long MaxSum, MaxLeft, MaxRight, MaxCenter;
long MaxCenterL, MaxCenterR, ThisSum;

if (Left == Right) {
if (A[Left] 0) return A[Left];
else return 0;
}

Center = (Left + Right) / 2;
MaxLeft = MaxSubseqSum(A,Left,Center);
MaxRight = MaxSubseqSum(A,Center+1,Right);

MaxCenterL = 0;
ThisSum = 0;
for (i=Center; i=Left; i--) {
ThisSum = ThisSum + A[i]; //이부분에서나는데 왜 일까요

MaxCenterL = max(MaxCenterL,ThisSum);
}

MaxCenterR = 0;
ThisSum = 0;
for (i=Center+1; i=Right; i++) {
ThisSum = ThisSum + A[i];
MaxCenterR = max(MaxCenterR,ThisSum);
}
MaxCenter = MaxCenterL + MaxCenterR;

MaxSum = max(max(MaxLeft,MaxRight),MaxCenter);
return MaxSum;
}

long max(long A, long B)
{
if(A=B)
return A;
else
return B;
}

신청하기