Longest Increasing Subsequence

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

Example 1:

Input: nums ={10,9,2,5,3,7,101,18}
Output: 4

Approach

Java

public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
        System.out.println(lengthOfLIS(nums));
    }

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

}

C++

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

int lengthOfLIS(vector<int>& nums) 
{
        int n=nums.size();
        vector<int> dp(n,1);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                      dp[i]=max(dp[i],1+dp[j]);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
             if(ans<dp[i])
                   ans=dp[i];
        return ans;
}

int main()
{
    vector<int> nums={10,9,2,5,3,7,101,18};
    cout<<lengthOfLIS(nums);
    return 0;
}