376. Wiggle Subsequence

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #medium
O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.
LeetCode Static

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

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

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

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

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

Exemplo:

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# solução

correspondente/original 
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++ solução

rascunho automático, revisar antes de enviar 
#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 solução

correspondente/original 
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

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

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

vagas ativas with overlapping task tags are mostradas.

Todas as vagas
Ainda não há vagas ativas.