力扣——6.动态规划

title: 动态规划

6、最长上升子序列

（1）采用动态规划，算法复杂度为O(n*n)

int lengthOfLIS(int* nums, int numsSize){
    int i, j, max=1;
    if(NULL==nums || 0==numsSize){
        return 0;
    }
    int *dp = (int*)malloc(numsSize*sizeof(int));
    memset(dp, 0, numsSize*sizeof(int));
    for(i=0; i<numsSize; ++i)
    {
        dp[i] = 1;
        for(j=0; j<i; ++j)
        {
            if(nums[j]<nums[i] && dp[i]<=dp[j]){
                dp[i] = dp[j]+1;
            }
            if(dp[i] > max){
                max = dp[i];
            }
        }
    }
    return max;
}

（2）贪心+二分查找，时间复杂度是O（n*log n）

注意理解 ：如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。（贪心）

int lengthOfLIS(int* nums, int numsSize){
    if(NULL==nums || 0==numsSize){
        return 0;
    }

    int len = 1, i;
    int *dp = (int*)malloc((numsSize+1)*sizeof(int));
    memset(dp, 0, (numsSize+1)*sizeof(int));
    dp[len] = nums[0];   
    for(i=1; i<numsSize; ++i)
    {
        if(nums[i] > dp[len]){
            dp[++len] = nums[i];
        } else{
            int left = 1, right = len, pos = 0;
            while(left <= right)
            {
                int mid = (left+right)>>1;
                if(dp[mid] < nums[i]){
                    pos = mid;
                    left = mid+1;
                } else{
                    right = mid-1;
                }
            }
            dp[pos+1] = nums[i]; 
        }
    }
    return len;
}

参考链接：http://cnblogs.com/BlairGrowing/p/12747603.html