알고리즘 과제#3-1 Maximum Subarray Problem

Maximum Subarray Problem 구현  

    입력파일 형식 : 원소개수 원소값들 

     예.    10 7 8 -9 6 8 -9 10 2 4 5 

 

[소스코드]

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define _FINITE -10000
int max_left = 0;
int max_right = 0;
 
int FindMaxCrossigSubarray(int A[], int low, int mid, int high) {
    int left_sum = _FINITE;
    int right_sum = _FINITE;
    int sum = 0;
    int i, j;
    for (i = mid; i >=low; i--) {
        sum = sum + A[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    sum = 0;
    for (j = mid + 1; j <= high; j++) {
        sum = sum + A[j];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = j;
        }
    }
    return  left_sum + right_sum;
}
 
int FINDMAXIMUMSUBARRAY(int A[], int low, int high) {
 
    int left_sum = 0;
    int right_sum = 0;
    int cross_sum = 0;
    int mid ;
    
    if (high == low)
        return A[low];
    else {
        mid = (low + high) / 2;
        left_sum= FINDMAXIMUMSUBARRAY(A, low, mid);
        right_sum= FINDMAXIMUMSUBARRAY(A, mid+1,high);
        cross_sum= FindMaxCrossigSubarray(A, low, mid,high);
        
    }
    if ((left_sum >= right_sum) && (left_sum >= cross_sum))
        return  left_sum;
    else if ((right_sum >= left_sum) && (right_sum >= cross_sum))
        return right_sum;
    else
        return cross_sum;
 
}
 
int main(void) {
    FILE *file;
    int num;//데이터수
    int max_sum = 0;
    int n = 0;
    int i, j;//반복
    int *data;//동적 메모리에서 사용할 정수형 포인터 선언
    //파일 열기
    
    file = fopen("input.txt", "r");
    //배열에 파일 입력
    if (file != NULL) {
        fscanf(file, "%d", &num);//배열 데이터 개수
        data = (int*)malloc(sizeof(int)*num);
 
        for (i = 0; i < num; i++) {
            fscanf(file, "%d", &data[i]);
        }
        printf("배열:");
        for (j = 0; j < num; j++) {
            
            printf("%d ", data[j]);
        }
    }
    
    max_sum = FINDMAXIMUMSUBARRAY(data, 0, num - 1);//최대합
    printf("\n시작 index:%d, 끝 index:%d", max_left, max_right);//출력
    printf("\n최대합:%d", max_sum);//출력
    fclose(file);
    free(data);
    return 0;
    
}