생활코딩(1)

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

 

Given an integer array, find the largest consecutive sum of elements.

 

예제}

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

 

-----------------------------------------------------------------------------------------------------------------------------------

#include 
#include 
#define SIZE 5

int maxx(int x, int y);   //함수 원형선언
void print();
int solution();

int main(void) {

int arry[SIZE],i,input;
int size = sizeof(arry) / sizeof(int);  //배열의 길이구하기 **

printf("Input: \n");
for (i = 0; i < size-1; i++) {   //배열값 입력
scanf("%d",&input);
arry[i] = input;
}

printf("Input: ");
print(arry,size);
printf("\n");
printf("Output: ");
printf("%d\n",solution(arry, size));

return 0;
}

void print(int arry[],int size) {   //값을 넣은 배열 화면에 출력
int i;

printf("[");
for (i = 0; i < size - 1; i++) {
printf("%d, ", arry[i]);
}
printf("]");
}
int solution(int arry[],int size) {   //연속되는 배열의 값중 최대값 구하기**
int maxSum = arry[0];
int currentSum = arry[0];
for (int i = 1; i < size-1; i++) {
currentSum = maxx(currentSum + arry[i], arry[i]); //인접한 두 수중 두 수의 합 보다 뒤가 크면 뒤 부터 시작
maxSum = maxx(currentSum, maxSum);                  //               두 수의 합 보다 뒤가 작으면 (앞)에서 부터 시작
}
return maxSum;
}

int maxx(int x, int y) {  //두수중 최댓값 구하기
int sum;
sum = (x >= y) ? x: y;
return sum;

}