LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열(Substring)을 구하는 경우.

Codeforces Round #613 Div2. B - Just Eat It! 1000Pts.

Problem - B - Codeforces

LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열을 구하는 경우.

수열은 v[1], v[2], ..., v[n], n=10만, v[x]는 [-10억,10억] 범위

---

1. 상태공간 정의

dp[x] = x번째 배열을 반드시 포함하는 최대값

 

2. 점화식

dp[x] = max(0, dp[x-1]) + v[x];

 

DP문제 자체는 쉬운데 한가지 조건이 있었으니 n개를 모두 포함하는 수열은 답에서 제외해야 했다.

그래서 나는 f(n-1)을 구하고 v[1]=0으로 만든 뒤 f(n)을 한번 더 구했다.

실수 할 부분이 많았음. ㅠ 앞으로는 주의하자.

 

 

 

 

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> v;
ll dp[100010];
int chk[200020];
 
ll f(int x, int z) {
    ll &ret = dp[x];
    if(x==1) return ret=v[x];
    if(chk[x] == z) return ret;
 
    return ret = max(0LL, f(x-1,z)) + v[x];
}
int main() {
    int tc; scanf("%d", &tc);
    for(int z=1; z<=tc; z++) {
        int n; scanf("%d", &n);
        v.clear(); v.resize(n+1, 0LL);
        ll yasser=0LL, adel=0LL;
        for(int i=1; i<=n; i++) {
            scanf("%lld", &v[i]);
            yasser += v[i];
        }
 
        f(n-1,z);
        for(int i=1; i<=n-1; i++) {
            adel = max(adel, dp[i]);
        }
 
        v[1]=0LL;
        f(n,z+tc);
 
        for(int i=2; i<=n; i++) {
            adel = max(adel, dp[i]);
        }
        if(yasser > adel) puts("YES");
        else puts("NO");
    }
    return 0;
}