# LeetCode 300: Longest Increasing Subsequence

## Problem Restatement

We are given an integer array `nums`.

We need to return the length of the longest strictly increasing subsequence.

A subsequence is formed by deleting some or no elements without changing the order of the remaining elements.

Strictly increasing means:

```python
nums[i] < nums[j] for all i < j in the subsequence
```

We do not need to return the subsequence itself, only its length.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Length of longest increasing subsequence |
| Constraint | Subsequence must preserve order |
| Constraint | Strictly increasing |

Function shape:

```python
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        ...
```

## Examples

For:

```python
nums = [10, 9, 2, 5, 3, 7, 101, 18]
```

One longest increasing subsequence is:

```python
[2, 3, 7, 101]
```

Answer:

```python
4
```

For:

```python
nums = [0, 1, 0, 3, 2, 3]
```

Longest increasing subsequence:

```python
[0, 1, 2, 3]
```

Answer:

```python
4
```

For:

```python
nums = [7, 7, 7, 7]
```

Answer:

```python
1
```

## First Thought: Dynamic Programming

Define:

```python
dp[i] = length of LIS ending at index i
```

Transition:

For each `i`, check all `j < i`:

```python
if nums[j] < nums[i]:
    dp[i] = max(dp[i], dp[j] + 1)
```

Code:

```python
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)
```

Time complexity is `O(n^2)`.

## Key Insight: Greedy + Binary Search

We maintain an array `tails`.

Interpretation:

- `tails[k]` = smallest possible tail of an increasing subsequence of length `k+1`.

We iterate through numbers and place each number into `tails` using binary search.

Rules:

- If `num` is larger than all tails, append it.
- Otherwise replace the first element in `tails` that is >= `num`.

This keeps subsequences flexible (small tails are better).

## Algorithm

```python
tails = []
```

For each number:

- Binary search position `pos`
- Replace or append

## Correctness

We never care about actual subsequence, only best possible ending values for each length.

Keeping smaller tails is always better because it allows more future extensions.

Binary search ensures each update maintains sorted order of `tails`.

The size of `tails` equals the longest increasing subsequence length.

## Complexity

| Metric | Value |
|---|---|
| Time | `O(n log n)` |
| Space | `O(n)` |

## Implementation

```python
import bisect

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []

        for num in nums:
            pos = bisect.bisect_left(tails, num)

            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num

        return len(tails)
```

## Code Explanation

We keep candidate subsequence tails:

```python
tails = []
```

For each number, we find where it fits:

```python
pos = bisect.bisect_left(tails, num)
```

If it extends the sequence:

```python
tails.append(num)
```

Otherwise we replace:

```python
tails[pos] = num
```

This maintains minimal tail values for each length.

Final answer:

```python
return len(tails)
```

## Testing

```python
def test_lis():
    s = Solution()

    assert s.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert s.lengthOfLIS([0, 1, 0, 3, 2, 3]) == 4
    assert s.lengthOfLIS([7, 7, 7, 7]) == 1
    assert s.lengthOfLIS([1, 2, 3, 4, 5]) == 5
    assert s.lengthOfLIS([5, 4, 3, 2, 1]) == 1

    print("all tests passed")

test_lis()
```