輸入一個整數數組疟丙，求所有連續(xù)子數組的和的最大值纵寝，例如{1, -2, 3, 10, -4, 7, 2, -5}拢锹，和最大的子數組為{3, 10, -4, 7, 2}卤恳，其和為18.
這個題目的一個解法，可以通過動態(tài)規(guī)劃的方式實現洞焙。即對于給定的n長的數組蟆淀，求其最大子數組和最大，即為求f(n)最大值澡匪。
- 當n=0時熔任，即數組長度只有1時，最大子數組長度必然就是該項本身唁情，即array[n];
- 當f(n-1)>0時疑苔，最大值必然是Math.max(array[n]+f(n-1), f(n-1))，其取決于array[n]是否>0;
- 當f(n-1)<0時甸鸟，最大值必然是array[n]惦费，因為f(n-1) + array[n] <= array[n]
實現算法如下：
private var maxSum = Int.MIN_VALUE
private fun getMaxSum(array: IntArray): Int {
getMaxSum(array, array.size - 1)
return maxSum
}
private fun getMaxSum(array: IntArray, index: Int): Int {
if (index == 0 || getMaxSum(array, index - 1) <= 0) {
return array[index]
}
val ms = array[index] + getMaxSum(array, index-1)
maxSum = Math.max(maxSum, ms)
return ms
}
測試用例如下：
object JavaTest {
@JvmStatic
fun main(args: Array<String>) {
println(getMaxSum(intArrayOf(1, -2, 3, 10, -4, 7, 2, -5)))
}
}
平時在練習過程中，隨著練習的增多抢韭，代碼也隨之增大薪贫，刪之可惜，本文所寫純粹是為記錄點滴的需要刻恭，如有雷同純屬巧合瞧省。
