Assignments & Coursework

### Dynamic Programming Solution: Longest Increasing Subsequence

We utilize patience sorting combined with binary search to achieve O(N log N) time complexity.

```python
import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        idx = bisect.bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
    return len(tails)
```

**Proof of Optimality:** Each tail[i] maintains the minimum ending value of an increasing subsequence of length i + 1. Since tails is strictly increasing, binary search is valid.