376. Wiggle Subsequence

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #medium

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним elementом и последовательность с двумя неравными elementами тривиально являются колеблющимися последовательностями.

На예제, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными.

В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю.

subsequence получается путем удаления некоторых elementов (возможно, нуля) из исходной последовательности с сохранением оставшихся elementов в их первоначальном порядке.

Дан 정수 배열 nums, return длину самой длинной колеблющейся подпоследовательности из nums.

예제:

Input: nums = [1,7,4,9,2,5]

Output: 6

Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

C# 해법

매칭됨/원본

public class Solution {
    public int WiggleMaxLength(int[] nums) {
        if (nums.Length < 2)
            return nums.Length;
        int[] up = new int[nums.Length];
        int[] down = new int[nums.Length];
        for (int i = 1; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.Max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.Max(down[i], up[j] + 1);
                }
            }
        }
        return 1 + Math.Max(down[nums.Length - 1], up[nums.Length - 1]);
    }
}

C++ 해법

자동 초안, 제출 전 검토

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int WiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2)
            return nums.size();
        vector<int>& up = new int[nums.size()];
        vector<int>& down = new int[nums.size()];
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = max(down[i], up[j] + 1);
                }
            }
        }
        return 1 + max(down[nums.size() - 1], up[nums.size() - 1]);
    }
}

Java 해법

매칭됨/원본

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i],down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i],up[j] + 1);
                }
            }
        }
        return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
    }
}

Algorithm

Для понимания этого подхода создайте два 배열а для динамического программирования, названных up и down. Эти 배열ы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием.

up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й element как последний element последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й element как последний element последовательности, заканчивающейся нисходящим колебанием.

up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м elementе. Чтобы find up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания.

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.