1
/** https://leetcode.com/problems/uncrossed-lines/
2
 * @param {number[]} nums1
3
 * @param {number[]} nums2
4
 * @return {number}
5
 */
6
var maxUncrossedLines = function (nums1, nums2) {
7
  // Array to hold the combination of connected numbers
8
  let dp = [];
9

10
  // We look up the connected numbers with matrix
11
  for (let i = 0; i < nums1.length; i++) {
12
    for (let j = 0; j < nums2.length; j++) {
13
      if (nums1[i] === nums2[j]) {
14
        dp.push([i, j]);
15
      }
16
    }
17
  }
18

19
  // Only 0 or 1 connected numbers found, return
20
  if (dp.length <= 1) {
21
    return dp.length;
22
  }
23

24
  // Array to count how many connected numbers in the matrix without crossing
25
  let count = Array(dp.length).fill(1);
26
  let out = count[0];
27

28
  // Count from the last connected numbers, for each connected number, count how many other connected numbers in front of it that will not crossed with current
29
  for (let i = dp.length - 2; i >= 0; i--) {
30
    for (let j = i + 1; j < dp.length; j++) {
31
      if (dp[i][0] < dp[j][0] && dp[i][1] < dp[j][1]) {
32
        count[i] = Math.max(count[i], count[j] + 1);
33
        out = Math.max(out, count[i]);
34
      }
35
    }
36
  }
37

38
  return out;
39
};