[알고리즘] 3202. Find the Maximum Length of Valid Subsequence II

Hyunjun Kim·2025년 7월 17일

DP DP + HashMap HashMap 부분수열

algorithm

목록 보기

7/8

Subsequence (부분 수열)

Subsequence란 원래 배열의 순서를 유지한 채, 일부 원소를 선택하여 만든 수열이다.

중간의 일부 요소를 건너뛸 수는 있지만,
원래의 순서는 반드시 유지해야 함.

문제

You are given an integer array nums and a positive integer k.
A **subsequence** sub of nums with length x is called valid if it satisfies:

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.


Return the length of the longest valid subsequence of nums.

예시

Example 1:

Input: nums = [1,2,3,4,5], k = 2

Output: 5

Explanation:

The longest valid subsequence is [1, 2, 3, 4, 5].


Example 2:

Input: nums = [1,4,2,3,1,4], k = 3

Output: 4

Explanation:

The longest valid subsequence is [1, 4, 1, 4].

제약 조건

Constraints:

2 <= nums.length <= 103
1 <= nums[i] <= 107
1 <= k <= 103

풀이

내 코드

정답 풀이 참고

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # dp[i][mod]: i번째 원소를 끝으로 하고, (a[j] + a[i]) % k == mod 인 최대 길이 subsequence
        dp = [dict() for _ in range(n)]
        max_len = 1

        for i in range(n):
            for j in range(i):
                mod = (nums[j] + nums[i]) % k
                prev_len = dp[j].get(mod, 1)  # 처음 두 원소부터 시작이라면 길이 2
                dp[i][mod] = max(dp[i].get(mod, 0), prev_len + 1)
                max_len = max(max_len, dp[i][mod])
            # 초기화: nums[i] 혼자 쓰는 경우는 subsequence 길이 1이므로 의미 없음
            # 첫 등장에 대해서는 아무런 이전이 없으니 저장 X

        return max_len

TEST

nums = [1,4,2,1,4]
k = 6


n = len(nums)
dp = dict()

for i in range(n):
        temp_dp = dp.copy()  # 현재 i번째 원소 기준으로 갱신
        for j in range(i):
            mod = (nums[i] + nums[j]) % k
            prev = dp.get(mod, 0)
            print("i:", i," j",j," mod : ", mod," prev: ",prev)
            temp_dp[mod] = max(temp_dp.get(mod, 0), prev + 1)
            print("temp_dp : ", temp_dp)
        dp = temp_dp
        print("dp : ", dp)

하나씩 프린트 해가면서 값이 어떻게 들어가는지 지켜보자.

dp :  {}
i: 1  j 0  mod :  5  prev:  0
temp_dp :  {5: 1}
dp :  {5: 1}
i: 2  j 0  mod :  3  prev:  0
temp_dp :  {5: 1, 3: 1}
i: 2  j 1  mod :  0  prev:  0
temp_dp :  {5: 1, 3: 1, 0: 1}
dp :  {5: 1, 3: 1, 0: 1}
i: 3  j 0  mod :  2  prev:  0
temp_dp :  {5: 1, 3: 1, 0: 1, 2: 1}
i: 3  j 1  mod :  5  prev:  1
temp_dp :  {5: 2, 3: 1, 0: 1, 2: 1}
i: 3  j 2  mod :  3  prev:  1
temp_dp :  {5: 2, 3: 2, 0: 1, 2: 1}
dp :  {5: 2, 3: 2, 0: 1, 2: 1}
i: 4  j 0  mod :  5  prev:  2
temp_dp :  {5: 3, 3: 2, 0: 1, 2: 1}
i: 4  j 1  mod :  2  prev:  1
temp_dp :  {5: 3, 3: 2, 0: 1, 2: 2}
i: 4  j 2  mod :  0  prev:  1
temp_dp :  {5: 3, 3: 2, 0: 2, 2: 2}
i: 4  j 3  mod :  5  prev:  2
temp_dp :  {5: 3, 3: 2, 0: 2, 2: 2}
dp :  {5: 3, 3: 2, 0: 2, 2: 2}

Subsequence 관련 용어 (알아두면 좋음)

용어	의미	예시
Contiguous subsequence	연속된 구간 (subarray)	`[2,3,4]`
Non-contiguous subsequence	건너뛰는 부분 수열	`[1,3,5]`
Ordered subsequence	순서 보존	`[2,4,5]`
Permutation	순서 변경 허용	`[1,2] → [2,1]` 가능

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
 

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

내 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        n = len(prices)
        max_p = 0
        for i in range(n):
            for j in range(i):
                gap = prices[i] - prices[j]
                if gap < 0:
                    pass
                if gap > max_p:
                    max_p = gap
        return max_p

Time Limit Exceeded 나왔다.

$O(n^2)$ 시간복잡도.

다시 푼 문제.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for i in prices:
            if min_price > i :
                min_price = i
            else:
                profit = i - min_price
                max_profit = max(max_profit, profit)
        return max_profit