[300] Longest Increasing Subsequence

其實是先寫它的衍伸題(但是不會寫XD)才看到這題
難怪我會把衍伸題弄成找長度(因為比較直覺QQ)
不過微慌張所以其實沒想很懂就看解法了
真是各種奧義QQ
只寫了 O(n^2), 據說可以弄成O(nlogn)
是每次存所有item裡的最小到最大(當時)
它其實不會是真正的subarray, 但是長度會是這題要的 LIS
且最後一個item也會是真正LIS時的最後結束的item
真是太玄了太玄了我沒時間了我們往下一題吧
(說是沒有時間但是慌張的來回跺步吃東西看電視消除焦慮神來也麻將試試手氣倒是有不少時間......)

Longest Increasing Subsequence
int lengthOfLIS(int* nums, int numsSize) {
    int i , j;
    int *len = malloc(sizeof(int)*numsSize);
    for(i=0;i<numsSize;i++)
    {
        len[i] = 1;
        for(j=0;j<i;j++)
        {
            if(nums[i]>nums[j])
            {
                if (len[i] < len[j]+1)
                    len[i] = len[j]+1;
            }
        }      
    }
    int max = 0;
    for(i=0;i<numsSize;i++)
    {
        if (len[i] > max)
            max = len[i];
    }
    return max;
}
這個解法是用一個array去存每個item可以有的LIS長度
一次用一往上加.
總覺得好像有寫過很類似的,
糾竟是哪題呢?!

然後發現可以加速一咪咪XD!!!!
喜歡把事情拆開一步一步做難道錯了嗎～～～～～～
int lengthOfLIS(int* nums, int numsSize) {
    int i , j;
    int max = 0;
    int *len = malloc(sizeof(int)*numsSize);
    for(i=0;i<numsSize;i++)
    {
        len[i] = 1;
        for(j=0;j<i;j++)
        {
            if(nums[i]>nums[j])
            {
                if (len[i] < len[j]+1)
                    len[i] = len[j]+1;  
            }
        }      
        if (len[i] > max)
            max = len[i];
    }
    return max;
}