300. Longest Increasing Subsequence

using System;
using System.Linq;
public class Solution {
    public int LengthOfLIS(int[] nums) {
        if (nums.Length == 0) return 0;
        int[] dp = new int[nums.Length];
        Array.Fill(dp, 1);
        for (int i = 1; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp.Max();
    }

#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 LengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int>& dp = new int[nums.size()];
        Array.Fill(dp, 1);
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp.Max();
    }

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }

function lengthOfLIS(nums) {
  if (nums.length === 0) {
    return 0;
  }

  const dp = Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        if not nums:
            return 0

        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

package main

import (
  "fmt"
  "math"
)

func lengthOfLIS(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  dp := make([]int, len(nums))
  for i := range dp {
    dp[i] = 1
  }

  for i := 1; i < len(nums); i++ {
    for j := 0; j < i; j++ {
      if nums[i] > nums[j] {
        dp[i] = int(math.Max(float64(dp[i]), float64(dp[j]+1)))
      }
    }
  }

  maxLength := 0
  for _, length := range dp {
    if length > maxLength {
      maxLength = length
    }
  }

  return maxLength
}

Algorithm

Инициализируйте mảng dp длиной nums.length, все elementы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается elementом с индексом i.

Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все elementы перед i). Для каждого elementа перед i, проверьте, меньше ли этот element, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).

return максимальное значение из dp.

😎