求连续子数组的最大和

输入一个整数数组，求所有连续子数组的和的最大值，例如{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)))
    }
}

平时在练习过程中，随着练习的增多，代码也随之增大，删之可惜，本文所写纯粹是为记录点滴的需要，如有雷同纯属巧合。