가장 큰 이어지는 원소들의 합
//문제
정수 배열(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$