배열 최대 연속 부분합 4가지 알고리즘

문제

https://www.acmicpc.net/problem/1912

1912번: 연속합

연속된 배열에서 합이 최대가 되는 연속 부분 합을 찾아라

 

ex)

 

풀이

1.완전탐색

 

2.부분합 배열 사용

 

3.분할정복

 

4.동적계획법

- 일단 f(i) = i를 끝으로 하는 배열의 최대합으로 생각하면

- f(i) = max(0, f(i-1)) + 현재 원소값이 된다.

 

무슨 소리냐면 이전까지 더해온 합이 음수라면,  현재 원소값을 더한 값 < 현재 원소값 이 확정이기 때문에 0으로 초기화 해준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> arr(n, 0);
    vector<int> cache(n, 0);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

	//초기화
    cache[0] = arr[0];
    int ret = cache[0];
    
    for (int i = 1; i < n; i++) {
        cache[i] = max(0, cache[i-1]) + arr[i];
        
        if(cache[i] > ret){
            ret = cache[i];
        }
    }

    printf("%d\n", ret);

    return 0;
}

 

// cache[i] = max(0, cache[i-1]) + arr[i]; 이부분을 cache[i] = max(cache[i-1]+arr[i], arr[i]); 이렇게 수정해도 될듯!

 

 

---

일단은 동적계획법만 정리했고 추후 수정할 포스팅입니다.