Longest Increasing Subsequence (LIS)?

int LIS(int[] nums)

int n = nums.Length;

int[] dp = new int[n];

Array.Fill(dp, 1);

int maxLen = 1;

for (int i = 1; i < n; i++)

for (int j = 0; j < i; j++)

if (nums[i] > nums[j])

dp[i] = Math.Max(dp[i], dp[j] + 1);

maxLen = Math.Max(maxLen, dp[i]);

return maxLen;

Explanation:

For each element, find LIS ending there by checking previous smaller elements.

Follow on: