[Leetcode] 1027. Longest Arithmetic Subsequence

1. 문제링크

https://leetcode.com/problems/longest-arithmetic-subsequence

Longest Arithmetic Subsequence - LeetCode

 

 

2. 키포인트

- dp사용한다. dp란? 내가 이번에 풀 문제는 현재 직전까지의 풀이 기록으로 해결할 수 있다는 것임

map을 저장할 vector를 만들고 사이즈를 nums배열과 동일하게 한다.

 

nums = [3,6,9];

여기서 2중 for문을 돌건데

바깥 for문은 i = 0, i < nums.size() 까지, 안쪽 for문은 j = 0, j < i가 될 때까지 순회한다

그리고 두 인덱스 값의 차이를 map에 기록한다

diff가 v[j]에 있다면 v[i][diff] = v[j]+1한다

 

i	j	diff	vector<un_map<int,int>> (i == j이면 업데이트 하지 않음)
0	0	-	-
1	0	3	v[1] = {3:2}
1	1	-	-
2	0	6	v[2] = {6:2}
2	1	3	v[2] = {6:2, 3:3}

 

 

3. solution

    class Solution {
    public:
        int longestArithSeqLength(vector<int>& nums) {
            int res = 0;
            int n = nums.size();
            vector<unordered_map<int,int>> v(n);

            for(int i = 0; i < n; i++){
                for(int j = 0; j < i; j++){
                    if(i == j) continue;
                    int diff = nums[i] - nums[j];
                    if(v[j].count(diff)){
                        v[i][diff] = v[j][diff] + 1;
                    } else {
                        v[i][diff] = 2;
                    }
                    // cout << "v[" << i << "],  diff : " << diff << ", v["<<i<<"] = {"<<diff<<":" << v[i][diff] <<"}"<< endl;
                    res = max(res, v[i][diff]);
                }
            }

            return res;
        }
    };