https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/

Idea1

定义状态： lis(i)表示以第i个数字为结尾的最长上升子序列长度

Code

  private static int LIS(int[] a) {
        int size=a.length;
        if(size==0) return 0;
        int[] result=new int[size+1];
       for(int i=1 ;i<size+1;i++)
       {
           result[i]=1;
       }
       for(int i=1;i<size;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(a[i]>a[j])
                {
                    result[i+1]=Math.max(result[i+1],1+result[j+1]);
                }
            }
        }
       int max=Integer.MIN_VALUE;
        for(int i=1 ;i<size+1;i++)
        {
            if(result[i]>max)
                max=result[i];
        }
        return max;
    }

Idea2

贪心算法
维护一个数组数组第0项 a[0]=nums[0];
遍历nums数组如果nums[i]>a[size-1] 则size++ 把nums[i]加入数组的最后一项
如果nums[i]<a[size-1]则找到第一个比nums[i]小的数将其下一位替换为nums[i]
想象一下如果我们以12为结尾这时候我们遇到了数字11 那么就应该把12替换为11 这样就可以保持贪心的正确性
以输入序列 [0, 8, 4, 12, 2，3,4] 为例：
第一步插入 0，d = [0]；
第二步插入 8，d = [0, 8]；
第三步插入 4，d = [0, 4]；
第四步插入 12，d = [0, 4, 12]；
第五步插入 2，d = [0, 2, 12]。
第六步插入3 ，d=[0,2,3]
第七步插入4 ,d=[0,2,3,4]
_
时间复杂度分析：遍历需要O(n)时间算法查找二分查找需要O(logN)时间算法
所以时间复杂度为O(NlogN)

Code

 public int lengthOfLIS(int[] nums) {
  int size=nums.length;
  if(size==0) return 0;
        int[] a=new int[size];
        a[0]=nums[0];
        int length=0;
        for(int i=1;i<size;i++)
        {
            if(nums[i]>a[length])
            {
                length++;
                a[length]=nums[i];
            }
            else
            {
                int l=0,r=length,pos=-1;
                while(l<=r) //二分查找 时间复杂度为O(logn)
                {
                    int mid=(l+r)>>1;
                    if(a[mid]<nums[i])
                    {
                        pos=mid;
                        l=mid+1;
                    }
                    else
                        r=mid-1;
                }
                a[pos+1]=nums[i];
            }
        }
        return length+1;
    }

最长上升子序列

Idea1

Code

Idea2

Code