11. Maximum Sum Subarray

<설명>

정수 어레이를 입력으로 받고,

그 합이 최대인 subarray의 합을 출력한다.

<Input>

첫번째 입력: 1과 100 사이의 정수 N

두번째 입력: [-100000, 100000]인 N개의 정수들

<Output>

합이 최대인 subarray의 합

<소스코드>

#include <stdio.h>
 
int arr[105];
 
int main (void)
{    
    int k=0;
    int i=0;
    int j=0;
    int N;
    int tem=0;
    int max=-10000000;
    scanf("%d",&N);
 
    for(i=0; i<N; i++)
    {
        scanf("%d",&arr[i]);
    }
    for(i=0; i<N; i++){
        for(j=0; j<=i; j++){
            for(k=j; k<=i; k++){
            tem=tem+arr[k];
            }
        if (tem>=max)
            max=tem;
        tem=0;
        }
    }
    
    printf("%d\n",max);
    
    return 0;
}

<설명>

index k는 j~i까지의 정수를 다 합하게 한다.

for loop을 2번 사용함으로써 (j,i)가 가질 수 있는 경우의 수를 다 갖게 한다.

길이가 0인, 즉 i==j일 수는 없다.

처음에 max를 저장할 때 정말 작은 숫자를 저장해 놓고 계속 더 큰 값을 max에 저장하여 출력한다.

이 방법은 for를 3번이나 겹쳐서 쓰기 때문에 계산 속도가 매우 느리다.

더 빠르게 해결할 수 있는 방법을 추후에 소개할 것이다.