maximum sum subarray(배열의 최대합 구간)

#include <stdio.h>

void max_subarray(int al[], int n) {

    int max_ending_here, max_so_far;

    int start_pos_x=0, start_pos, end_pos, i;

    max_ending_here=al[0];

    max_so_far=al[0];

    for(i=1;i<n;i+=1) {

        if(al[i]>max_ending_here+al[i]) {

            start_pos_x=i;

            max_ending_here=al[i];

        } else {

            max_ending_here=al[i]+max_ending_here;

        }

        if(max_so_far<max_ending_here) {

            start_pos=start_pos_x;

            end_pos=i;

            max_so_far=max_ending_here;

        } 

    }

    printf("start_pos=%d end_pos=%d\n", start_pos,end_pos);

    for(i=start_pos;i<end_pos+1;i+=1) {

        printf("%d ", al[i]);

    }

    printf("sum=%d\n", max_so_far);

}

int main() {

    int al[100]={0,};

    int i=0, x;

    while(1) {

        scanf("%d", &x);

        if(x==0) break;

        al[i]=x;

        i+=1;

    }

    max_subarray(al, i);

    return 0;

}

============================================================

Maximum sum subarray problem

Ulf Grenander of Brown University in 1977

Linear time algorithm by Jay Kadane of Carnegie-Mellon University 1984

0이 입력될 때까지 정수(20개 이하)들을 입력 받아, 연속해서 입력된

임의의 개수의 정수들의 합이 최대가 되는 경우를 출력하는 프로그램을

작성하시오.

단 합이 최대가 되는 구간의 둘 이상인 경우에는 가장 처음에 나오는

구간을 출력하라.

예:

10 -5 -12 4 -13 11 7 -3 7 -10 5 0

==> 11 7 -3 7

10 -5 -12 4 -3 11 7 -3 7 -10 5 0

==> 4 -3 11 7 -3 7

1 1 -5 2 0

==> 1 1

-3 -1 0

==> -1

###################################################################

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, 

computing at each position the maximum (positive sum) subarray 

ending at that position. This subarray is either empty (in which case 

its sum is zero) or consists of one more element than the maximum 

subarray ending at the previous position. 

The algorithm only needs to keep track of the ending position 

because the implied starting position is just after the last position 

the sum went negative, and you can always get a higher sum 

by dropping any negative-sum prefix. 

Thus, the problem can be solved with the following code, 

expressed here in Python:

def max_subarray(A):

    max_ending_here = max_so_far = A[0]

    for x in A[1:]:

        max_ending_here = max(x, max_ending_here + x)

        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

https://en.wikipedia.org/wiki/Maximum_subarray_problem