Java O(n^2). Non DP

  • 0
    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;
            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;
            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.