1027. Longest Arithmetic Subsequence

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

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Если задан array nums целых чисел, return длину самой длинной арифметической подпоследовательности в nums. Примечание: subsequence - это array, который может быть получен из другого arrayа путем удаления некоторых или ни одного elementа без изменения порядка оставшихся elementов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).

Example:

Input: nums = [3,6,9,12]

Output: 4

C# solution

matched/original

public class Solution {
    public int LongestArithSeqLength(int[] nums) {
        if (nums.Length == 0) return 0;
        
        var dp = new Dictionary<int, int>[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            dp[i] = new Dictionary<int, int>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].TryGetValue(diff, out int length)) {
                    dp[i][diff] = length + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = Math.Max(maxLength, dp[i][diff]);
            }
        }
        
        return maxLength;
    }
}

C++ solution

auto-draft, review before submit

#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 LongestArithSeqLength(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        
        var dp = new unordered_map<int, int>[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            dp[i] = new unordered_map<int, int>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].TryGetValue(diff, out int length)) {
                    dp[i][diff] = length + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = max(maxLength, dp[i][diff]);
            }
        }
        
        return maxLength;
    }
}

Java solution

matched/original

public class Solution {
    public int longestArithSeqLength(int[] nums) {
        if (nums.length == 0) return 0;
        
        int n = nums.length;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                int length = dp[j].getOrDefault(diff, 1) + 1;
                dp[i].put(diff, length);
                maxLength = Math.max(maxLength, length);
            }
        }
        
        return maxLength;
    }
}

JavaScript solution

matched/original

class Solution {
    longestArithSeqLength(nums) {
        if (nums.length === 0) return 0;
        
        const dp = Array(nums.length).fill(0).map(() => new Map());
        let maxLength = 0;
        
        for (let i = 0; i < nums.length; i++) {
            for (let j = 0; j < i; j++) {
                const diff = nums[i] - nums[j];
                const length = (dp[j].get(diff) || 1) + 1;
                dp[i].set(diff, length);
                maxLength = Math.max(maxLength, length);
            }
        }
        
        return maxLength;
    }
}

Algorithm

Инициализация переменных:

Создайте array словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на elementе i с разностью d.

Заполнение arrayа dp:

Пройдитесь по каждому elementу arrayа nums.

Для каждого elementа nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].

Обновите dp[i][d] на основе значения dp[j][d].

Поиск максимальной длины:

Пройдите по arrayу dp и find максимальное значение среди всех значений dp[i][d].

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.