本文參考
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
}
創作內容
[Kotlin]Longest Increasing Subsequence
未分類 (6)