백준 25289, 가장 긴 등차 부분 수열

개요

문제 링크
골드 5, DP
부분 수열 중 가장 긴 등차 수열의 길이

---

접근

1. LIS를 쓰는 문제인가? 했다가 골드5에 O(nlogn)을 묻지는 않을 것 같아서 pass. A가 100까지면 아하, A를 중심으로 루프를 돌려야 하는구나.
2. dp[i][j] 에 들어가는 건 공차가 i이면서 끝값이 j인 등차수열의 최대 길이
3. 업데이트는? 등차수열의 이전항이 끝값인 경우의 최대 길이 + 1 해주면 됨. 즉, dp[i][j] = dp[i][j-i]+1
4. 주의할 점은 음수 공차도 되므로 음수 인덱스 방지를 해줘야 하는 것.

---

Pseudo code

for (i = 0~n)
    for (j = -A~A)
        v = a[i]
        dp[j][v] = dp[j][v-j]+1
answer = max(dp)

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int A = 100;
const int M = 300;
int dp[M][M];

int main() {
    int n;
    cin >> n;
    int a;
    int ans = 1;
    for (int i=0; i<n; i++) {
        cin >> a;
        dp[a+A][a] = 1;
        for (int j=-A; j<A; j++) {
            int k = (a-j>0?a-j:0);
            dp[j+A][a] = dp[j+A][k]+1;
            ans = max(ans, dp[j+A][a]);
        }
    }
    cout << ans;
}