創作內容

0 GP

[Kotlin]Longest Increasing Subsequence

作者:燐火│2021-07-10 21:17:39│巴幣:0│人氣:51
本文參考

Given an integer array
nums, return the length of the longest strictly increasing subsequence.
給予一個Int陣列,回傳該陣列的最大遞增序列長度
--

遞增序列,簡單來說就是陣列中由小到大的數字串

假設
[2,5,3]
它的遞增序列可以是
[2, 5]或者[2, 3]
--
[4,1,7]
它的遞增序列可以是
[4,7]或者[1,7]
--
所以一個陣列可以有很多遞增序列
--

最大遞增序列的話就是指最長的遞增序列
*要注意的是最大遞增序列可能不只有一種

假設
[10,9,2,5,3,7,101,18]
它的最大遞增序列是
[2,3,7,101]或者[2,3,7,18]
那答案就是4
--
[3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12]
最大遞增序列
3, 4, 5, 6, 7, 12
答案是6
--

把A[position]作為目前指到的數字
把list[position]視為第幾個序列
我們可以歸類出它的三種模式
1.當A[position]比list[0]還要小的時候, 它可能會有新的最大序列
2.當A[position]比list最後一個數字還大的時候, 序列增加
3.當A[position]比list內的某個序列最後值小,將A[position]最為新的序列最後值,可能有更大的最大序列
--

舉個詳細的解題過程
以[3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12]為例
            --A[0] = 3
            3
            --A[1] = 5
            3
            3, 5
            --A[2] = 6
            3
            3, 5
            3, 5, 6
            --A[3] = 2
            2
            3, 5
            3, 5, 6
            --A[4] = 5
            2
            3, 5
            3, 5, 6
            --A[5] = 4
            2
            3, 4
            3, 5, 6
            --A[6] = 19
            2
            3, 4
            3, 4, 6
            3, 4, 6, 19
            --A[7] = 5
            2
            3, 4
            3, 4, 5
            3, 4, 6, 19
            --A[8] = 6
            2
            3, 4
            3, 4, 5
            3, 4, 5, 6
            --A[9] = 7
            2
            3, 4
            3, 4, 5
            3, 4, 5, 6
            3, 4, 5, 6, 7
            --A[10] = 12
            2
            3, 4
            3, 4, 5
            3, 4, 5, 6
            3, 4, 5, 6, 7
            3, 4, 5, 6, 7, 12

答案是6
--

程式實作
為簡化程式,intList只儲存每個序列的最後值
fun lengthOfLIS(nums: IntArray): Int {
    var intList : MutableList<Int> = arrayListOf()
    intList.add(nums[0])
    for (position in 1 until nums.size){
        when {
            //小於陣列初始值,作為新的陣列可能性基準
            intList[0] > nums[position] -> {
                intList[0] = nums[position]
                println("list[0]: ${nums[position]}")
            }
            //大於陣列最後值,陣列長度+1
            intList.last() < nums[position] -> {
                print(intList.last())
                println(" < ${nums[position]}")
                intList.add(nums[position])
                println("list[${intList.size-1}]: ${nums[position]}")
            }
            else -> {
                for (i in 1 until intList.size) {
                    //序列最後值大於A[position],且A[position]大於序列的倒數第二個值
                    if (intList[i] > nums[position] && intList[i - 1] < nums[position]) {
                        intList[i] = nums[position]
                        println("list[$i]: ${nums[position]}")
                    }
                }
            }
        }
    }
    return intList.size
}
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=5204245
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★d19910106 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:20210108隨筆...

追蹤私訊切換新版閱覽

作品資料夾

san0196親愛的巴友們
在界世界?的那些事 第12話更新囉,歡迎閱讀與指教。看更多我要大聲說昨天18:37


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】