[JAVA 문제 풀이] 384. Find the Maximum Length of Valid Subsequence II

Find the Maximum Length of Valid Subsequence II - LeetCode

Can you solve this real interview question? Find the Maximum Length of Valid Subsequence II - 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

https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-ii/description/

정수 배열 'nums'와 양의 정수 k가 주어집니다.
길이가 'x'인 'nums'의 후속 'sub'가 다음을 만족하면 유효하다고 합니다:

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

가장 긴 유효한 수열의 길이를 반환합니다.

제약 조건:
* 2 <= nums.length <= 103
* 1 <= nums [i] <= 107
* 1 <= k <= 103

다른 사람의 코드 + 내가 작성한 코드

import java.util.*;

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        // dp[i][mod]는 nums[i]를 마지막으로 하는 부분 수열 중,
        // (연속된 두 수의 합 % k)가 mod인 경우의 최대 길이를 저장
        int[][] dp = new int[n][k];   
        int result = 1; // 결과는 최소 1 (자기 자신 하나만으로도 부분 수열 가능)

        // 모든 위치에 대해 mod별 길이를 1로 초기화 (각 숫자 하나만 있는 경우)
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 1);
        }

        // i번째 숫자를 마지막 원소로 하는 부분 수열 찾기
        for (int i = 0; i < n; i++) {
            // i 이전의 숫자 j를 탐색
            for (int j = 0; j < i; j++) {
                // nums[j]와 nums[i]의 합을 k로 나눈 나머지
                int mod = (nums[j] + nums[i]) % k;
                // dp[j][mod]에 +1 한 값과 현재 dp[i][mod] 값을 비교해 최대값으로 갱신
                dp[i][mod] = Math.max(dp[i][mod], dp[j][mod] + 1);
                // 결과값 갱신
                result = Math.max(result, dp[i][mod]);
            }
        }

        // 가장 긴 유효한 부분 수열의 길이 반환
        return result;
    }
}