[LeetCode 3201] Find the Maximum Length of Valid Subsequence I

문제 바로가기

Description

---

You are given an integer array nums.

A subsequence sub of nums with length x is called valid if it satisfies:

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

Return the length of the longest valid subsequence of nums.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1

---

• Input: nums = [1,2,3,4]
• Output: 4
• Explanation:
  • The longest valid subsequence is [1, 2, 3, 4].

Example 2

---

• Input: nums = [1,2,1,1,2,1,2]
• Output: 6
• Explanation:
  • The longest valid subsequence is [1, 2, 1, 2, 1, 2].

Example 3

---

• Input: nums = [1,3]
• Output: 2
• Explanation:
  • The longest valid subsequence is [1, 3].

Constraints

---

• 2 <= nums.length <= 2 * 10^5
• 1 <= nums[i] <= 10^7

Hint

---

Hint 1

  The possible sequence either contains all even elements, all odd elements, alternate even odd, or alternate odd even elements.
	

Hint 2

  Considering only the parity of elements, there are only 4 possibilities and we can try all of them.
	

Hint 3

  When selecting an element with any parity, try to select the earliest one.
	

Code

---

내 제출

---

class Solution {
    public int maximumLength(int[] nums) {
        int k = 2;
        int[][] f = new int[k][k];
        int ans = 0;
        for (int x : nums) {
            x %= k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x][y] = f[y][x] + 1;
                ans = Math.max(ans, f[x][y]);
            }
        }
        return ans;
    }
}

Runtime	Memory
6 ms	63.9 MB

다른 풀이

---

class Solution {
    public int maximumLength(int[] nums) {
        return solve(nums);
    }

    int solve(int[]arr){
        int e =0;
        int o = 0;
        for(int ele : arr){
            if(ele%2==0){
                e++;
            }else{
                o++;
            }
        }

        int ans = Math.max(e,o);
        int pairty = arr[0]%2;
        int oddEven = 1;

        for(int i = 1;i<arr.length;i++){
            if(arr[i]%2 != pairty){
                oddEven++;
                pairty = arr[i]%2;
            }
        }

        return Math.max(oddEven,ans);
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/3200-3299/3201.Find%20the%20Maximum%20Length%20of%20Valid%20Subsequence%20I/Solution.java