300.Longest Increasing Subsequence

Posted on | In

Test cases

1
2
3
4
5
6
7
[10,9,2,5,3,7,101,18]
[2,5,3,4]
[2,5,3,4,6]
[2,3,4,5]
[5,4,3,2]
[0]
[1,1,1,1]

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int lengthOfLIS(int[] nums) {
        
        int len = nums.length;
        if (len < 2) return len;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++) {
            map.put(i, 1);
        }
        
        int max = 1;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (nums[j] < nums[i]) {
                    int bigger = map.get(i) > map.get(j) + 1 ? map.get(i) : map.get(j) + 1;
                    map.put(i, bigger);
                }
            }
            max = max > map.get(i)? max :  map.get(i);
        }
        return max;
    }
}