leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

longest_increasing_subseq.c (851B)

 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
// 300. Longest Increasing Subsequence
#include "leetcode.h"

/*
 * given an integer array 'nums', return the length of the longest strictly
 * increasing subsequence.
 */

int lengthOfLIS(int *nums, int nums_size) {
  int dp[nums_size], max_len = 0;
  for (int i = 0; i < nums_size; ++i)
    dp[i] = 1;
  for (int i = 0; i < nums_size; ++i)
    for (int j = 0; j < i; ++j)
      if (nums[i] > nums[j])
        dp[i] = fmax(dp[i], dp[j] + 1);
  for (int i = 0; i < nums_size; ++i)
    max_len = fmax(max_len, dp[i]);
  return max_len;
}

int main() {
  int n1[] = {10, 9, 2, 5, 3, 7, 101, 18}, n2[] = {0, 1, 0, 3, 2, 3},
      n3[] = {7, 7, 7, 7, 7, 7, 7};
  printf("%d\n", lengthOfLIS(n1, ARRAY_SIZE(n1))); // expect: 4
  printf("%d\n", lengthOfLIS(n2, ARRAY_SIZE(n2))); // expect: 4
  printf("%d\n", lengthOfLIS(n3, ARRAY_SIZE(n3))); // expect: 1
}