[BOJ] 16512 Maximum Subarrays

문제

16512번: Maximum Subarrays

You may have heard of the “maximum subarray problem” from your university’s undergraduate algorithms course. The problem goes like this: You are given an array A of n integers, and the task is to find a contiguous subarray of A whose sum is maximum. For example, in the array below:

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

풀이

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long ll;
using namespace std;
 
int n, m;
vector<int> v;
ll dp[5000][5000][2];
 
ll go(int ix, int cnt, int flag) {
    if (ix == n) {
        if (flag == 0) cnt++;
        if (cnt == m) return 0;
        return -1e18;
    }
    if (dp[ix][cnt][flag] != -1) return dp[ix][cnt][flag];
    ll ret;
    if (flag) {
        ret = max(go(ix + 1, cnt, 1), go(ix + 1, cnt, 0) + v[ix]);
        ret = max(ret, go(ix + 1, cnt + 1, 1) + v[ix]);
    } else {
        ret = max(go(ix + 1, cnt, 0) + v[ix], go(ix + 1, cnt + 1, 1) + v[ix]);
    }
    return dp[ix][cnt][flag] = ret;
}
 
int main() {
    scanf("%d %d", &n, &m);
    memset(dp, -1, sizeof(dp));
    ll a;
    for(int i = 0; i < n; i++) {
        scanf("%lld", &a);
        v.push_back(a);
    }
    printf("%lld", go(0, 0, 1));
}