Longest Increasing Subsequence (LIS) int LIS(int[] nums) { int n = nums.Length; int[] dp = new int[n];?

rray.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: