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

**Approach**

**O(N^2) Solution**

To find the length of the longest strictly increasing subsequence in an integer array `nums`

, we can use the dynamic programming approach. Here’s how it works:

- We create an array
`dp`

of the same length as`nums`

, where`dp[i]`

represents the length of the longest increasing subsequence that ends at index`i`

. - We initialize each element of
`dp`

to 1 because the longest increasing subsequence that ends at index`i`

must contain at least the element at index`i`

itself. - For each index
`i`

from`1`

to`n-1`

where`n`

is the length of`nums`

, we compare`nums[i]`

with all the elements before it, that is, from`0`

to`i-1`

. If`nums[i]`

is greater than`nums[j]`

, where`0 <= j < i`

, then we can include`nums[i]`

in the longest increasing subsequence that ends at index`i`

, which would have a length of`dp[j]+1`

. We update`dp[i]`

to the maximum of all such values. - Finally, we return the maximum value in the
`dp`

array as the length of the longest strictly increasing subsequence in the`nums`

array.

Here’s the Python code that implements the above approach:

```
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
```

Example

```
>>> nums = [10,9,2,5,3,7,101,18]
>>> lengthOfLIS(nums)
4
```

In the above example, the longest strictly increasing subsequence is `[2, 3, 7, 101]`

, which has a length of 4.

**O(N log N) Solution**

To improve the time complexity of the dynamic programming approach to `O(n log n)`

, we can use a modified version of the binary search algorithm.

Here’s the modified algorithm:

- We create an empty array
`tails`

of length`n`

, where`n`

is the length of`nums`

.`tails[i]`

represents the smallest tail element of all increasing subsequences of length`i+1`

that we have found so far. - We initialize
`tails[0]`

to be the first element of`nums`

. - For each element
`num`

in`nums`

starting from index`1`

, we perform a binary search in the`tails`

array to find the largest index`i`

such that`tails[i]`

is less than or equal to`num`

. - If we find such an index
`i`

, we update`tails[i]`

to be`num`

, as we have found a longer increasing subsequence of length`i+1`

. - If we do not find such an index
`i`

, it means that`num`

is greater than all the elements in the`tails`

array, and we can append`num`

to the end of the`tails`

array to create a new longest increasing subsequence of length`i+1`

. - Finally, we return the length of the
`tails`

array as the length of the longest strictly increasing subsequence in the`nums`

array.

Here’s the Python code that implements the above algorithm:

```
def lengthOfLIS(nums):
n = len(nums)
tails = [0] * n
size = 0
for num in nums:
left, right = 0, size
while left < right:
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid
tails[left] = num
size = max(size, left + 1)
return size
nums = [10,9,2,5,3,7,101,18]
print(lengthOfLIS(nums)) # Output: 4
```

In the above example, the longest strictly increasing subsequence is `[2, 3, 7, 101]`

, which has a length of 4. The time complexity of this algorithm is `O(n log n)`

.