1 Problem F : 연속부분합 찾기

N개의 정수를 담고 있는 배열에서, 가능한 연속 부분합을 구하는 프로그램을 작성하라

입력에 대한 가장 큰 연속 부분합을 출력한다

 

#include <stdio.h>

int N, arr[100005], ans;

int Max(int x, int y) { return x > y ? x : y; } // MAX 함수
int main()
{
	scanf("%d", &N); // 숫자를 입력 받고
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]); // 하나씩 넣는데,
		if (arr[i - 1] > 0) arr[i] += arr[i - 1]; // 양수이면 누적값을 저장함
		ans = Max(ans, arr[i]); // 가장 큰 수를 저장함
	}
	printf("%d\n", ans);
	return 0;
}

4 1 2 -2 4 10 3 -4 0 1 7 -4 13 -9 8 -3

5 17