输入一个整数数组，求所有连续子数组的和的最大值，例如{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为{3, 10, -4, 7, 2}，其和为18.
这个题目的一个解法，可以通过动态规划的方式实现。即对于给定的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)))
}
}
平时在练习过程中，随着练习的增多，代码也随之增大，删之可惜，本文所写纯粹是为记录点滴的需要，如有雷同纯属巧合。
