2ms Java Solution


  • 0
    R
    public class Solution {
        public int lengthOfLIS(int[] a) {
            int n = a.length;
    		int[] tail = new int[n];
    		int[] prev = new int[n];
    
    		int len = 0;
    		for (int i = 0; i < n; i++) {
    			int pos = lower_bound(a, tail, len, a[i]);
    			if (pos == len) {
    				++len;
    			}
    			prev[i] = pos > 0 ? tail[pos - 1] : -1;
    			tail[pos] = i;
    		}
    		return len;
        }
        int lower_bound(int[] a, int[] tail, int len, int key) {
    		int lo = -1;
    		int hi = len;
    		while (hi - lo > 1) {
    			int mid = (lo + hi) / 2;
    			if (a[tail[mid]] < key) {
    				lo = mid;
    			} else {
    				hi = mid;
    			}
    		}
    		return hi;
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.