가장 큰 이어지는 원소들의 합

//문제

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).

 

//예제

Input: [-1, 3, -1, 5]

Output: 7     // 3 + (-1) + 5

 

Input: [-5, -3, -1]

Output: -1     // -1

 

Input: [2, 4, -2, -3, 8]

Output: 9     // 2 + 4 + (-2) + (-3) + 8

//코딩

//

//  main.c

//  program

//

//  Created by Eon on 7/26/18.

//  Copyright © 2018 Eonseok Yim. All rights reserved.

//

#include <stdio.h>

int math_max(int a, int b) {

    if (a < b) {

        return b;

    }

    else return a;

}

int solution(int *array, int length) {

    int max = array[0];

    int current = array[0];

    for (int i=1; i<length; i++) {

        current = math_max(current + array[i], array[i]);

        max = math_max(current, max);

    }

    return max;

}

int main(int argc, const char * argv[]) {

    int len = 4;

    int array[10] = {-1, 3, -1, 5};

    

    printf("max: %d\n", solution(array, len));

    return 0;

}

//실행

Eons-MacBook-Pro:Debug eon$ ls

program

Eons-MacBook-Pro:Debug eon$ ./program 

max: 7

Eons-MacBook-Pro:Debug eon$