Java O(n^2). Non DP


  • 0
    Q
    public class Solution {
        public int lengthOfLIS(int[] nums) {
            List<ValAndIndex> l = new ArrayList<ValAndIndex>();
            for (int i=0;i<nums.length;i++)
                l.add(new ValAndIndex(nums[i],i));
            int max = l.isEmpty()?0:1;
            Collections.sort(l);
            for (int i=0;i<nums.length;i++){
            	ValAndIndex v1 = l.get(i);
            	for (int j=i+1;j<nums.length;j++){
            		ValAndIndex v2 = l.get(j);
            		if (v2.val>v1.val && v2.idx>v1.idx&& v2.cnt<=v1.cnt){
            			v2.cnt = v1.cnt+1;
            			max=v2.cnt>max?v2.cnt:max;
            		}
            	}
            }
            return max;
        }
        private class ValAndIndex implements Comparable{
            public ValAndIndex(int val, int idx){
                this.val = val; this.idx = idx;
            }
            public int compareTo(Object o){
                return val -  ((ValAndIndex)o).val;
            }
            private int val,idx,cnt=1;
        }
    }

Log in to reply
 

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