Best Team With No Conflicts LeetCode solution in Java

1
class Solution {
2
  int res = 0;
3

4
  public int bestTeamScore(int[] scores, int[] ages) {
5
    int len = scores.length;
6
    int[][] team = new int[len][2];
7
    for (int i = 0; i < len; i++) {
8
      team[i][0] = ages[i];
9
      team[i][1] = scores[i]; // team is [age, score]
10
    }
11
    // double sort first by age then by score, then we can traverse from young to old
12
    Arrays.sort(team, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
13

14
    int[] dp = new int[len];
15
    // dp is the max sum for all sequences (not necessarily consecutive) ending in current idx
16
    dp[0] = team[0][1];
17
    for (int i = 1; i < len; i++) {
18
      int max = team[i][1]; // At least it could start a new sequence by itself without extend
19
      // for each current idx, go visit all previous index to grow the sequences
20
      for (int j = 0; j < i; j++) {
21
        if (team[i][1] >= team[j][1]) {
22
          max = Math.max(max, dp[j] + team[i][1]);
23
        }
24
      }
25
      dp[i] = max;
26
    }
27

28
    int res = 0;
29
    for (int num : dp) {
30
      res = Math.max(res, num);
31
    }
32

33
    return res;
34
  }
35
}