generated from eyamenko/dotnet-template-repository
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Problem45.cs
37 lines (32 loc) · 1.05 KB
/
Problem45.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
namespace LeetCode;
/// <summary>
/// <see href="https://leetcode.com/problems/longest-increasing-subsequence/">Longest Increasing Subsequence</see>.
/// </summary>
public static class Problem45
{
/// <summary>
/// Given an integer array nums, return the length of the longest strictly increasing subsequence.
/// Time complexity: O(n^2).
/// Space complexity: O(n).
/// </summary>
/// <param name="nums">Array to traverse.</param>
/// <returns>Length of the longest strictly increasing subsequence.</returns>
public static int LengthOfLIS(int[] nums)
{
var maxLength = 0;
var lengths = new int[nums.Length];
for (var i = nums.Length - 1; i >= 0; i--)
{
for (var j = i + 1; j < nums.Length; j++)
{
if (nums[i] < nums[j])
{
lengths[i] = Math.Max(lengths[i], lengths[j]);
}
}
lengths[i]++;
maxLength = Math.Max(maxLength, lengths[i]);
}
return maxLength;
}
}