Longest increasing subsequence

Challenge

Implement:

int lis(const int *a, int n);

Return the length of the longest strictly increasing subsequence of a[0..n-1].

Input format

Array a, count n.

Output format

LIS length.

Constraints

O(n^2) DP is fine for the tested sizes.

Starter code

#include <stddef.h>
/* Length of the Longest strictly Increasing Subsequence of a[0..n-1]. */
int lis(const int *a,int n){ (void)a;(void)n; return 0; }

Common mistakes

Requiring contiguity — a subsequence may skip elements.

Edge cases to handle

n==0 -> 0; a flat array -> 1.

Background lessons

• LIS & Kadane's algorithm