Leetcode 300 Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Input: nums = [0,1,0,3,2,3]
Output: 4

Input: nums = [7,7,7,7,7,7,7]
Output: 1

• Bu soruda bize bir liste veriliyor.Ve sıralı olarak artarak giden maksimum kaç sayı olduğu soruluyor.
• Örneğin [10,9,2,5,3,7,18] listesinde [2,3,7,18] artarak ilerleyen sayı kümesi elemanı da 4.
• Bu soruyu dinamik programlama ile çözebiliriz.
• En sondan başlayarak birer birer tüm sayıları gezelim.
• [18] artarak ilerleyen sayı kümesi elemanı 1 indexi 6 olduğu için lis[6] = 1
• [7,18] artarak ilerleyen sayı kümesi elemanı 2 peki bu 2 yi nasıl hesaplarız lis[5] = max(1,1+lis[6]) yani lis[5] = 2
• [3,7,18] artarak ilerleyen sayı kümesi elemanı 3 peki bu 3 ü nasıl hesaplarız lis[4] = max(1,1+lis[5],1+lis[6]) yani lis[4] = 3
• [5,3,7,18] artarak ilerleyen sayı kümesi elemanı 3 peki bu 3 ü nasıl hesaplarız buradaki dikkat edilmesi gereken şey lis[4] bu karşılaştırmaya koyulmadı çünkü 3 5 ten küçük ve istediğimiz listeye uymuyor o yüzden lis[3] = max(1,1+lis[5],1+lis[6]) yani lis[3] = 3
• Bu şekilde 0. indexe kadar karşılaştırma yapılarak gidilir ve her index için artarak giden maksimum kaç sayı olduğu bulunur.Sonra da bunlardan en büyüğü dönülür.

    def lengthOfLIS(self, nums: List[int]) -> int:
        LIS = [1] * len(nums)
        
        for i in range(len(nums) - 1,-1,-1):
            for j in range(i+1,len(nums)):
                if nums[i] < nums [j]:
                    LIS[i] = max(LIS[i], 1 + LIS[j])
        return max(LIS)