题解 | #子数组的最大累加和问题#

解题思路

一般求子数组的最大xx问题，都是可以拆解成一个个子问题，那么就考虑动态规划。
即子问题的解，其子结构逐步迭代也是一个整个问题的解。

状态转移的思路（或子问题的思路）

思路转化方式

1. 当移到位置i时，考虑是否与arr[i]进行累加，且结果是更大
2. 如果位置i-1的值是负数，说明没必要累加，可以重新从arr[i]开始重新计算累加和
3. 因为dp[i-1]+arr[i] < arr[i]，我们取两者的更大值arr[i]
4. 最关键的状态转移方式是:max(0, dp[i-1])
   • 与0比较，是因为一旦第i-1个位置的最大和是负数
   • 负数与arr[i]会导致和更小
   • 这样max(0, dp[i-1]) + arr[i] 就是位置i的最大累加和

以上是整个思路的核心

解法一

空间复杂度为O(n)的方式，定义一个dp数组存储每一步i位置的最大累加和，然后取数组最大值

/**
 * max sum of the subarray
 * @param arr int整型一维数组 the array
 * @return int整型
*/
func maxsumofSubarray( arr []int ) int {
    // write code here
    //边界条件处理
    if len(arr) == 0 {
        return 0
    }
    /*
      状态转移的思路（或子问题的思路）
      与数组第i个位置arr[i]相加后，取前面i-1的子数组中求和最大值
      最关键的最大值求法：max(0, dp[i-1])
       - 与0比较，是因为一旦第i-1个位置的最大和是负数
       - 负数与arr[i]会导致和更小
    */

    //定义一个一维的数组，每个位置存到i位置的最大累加和
    dp := make([]int, len(arr))
    //第0个位置初始化
    dp[0] = arr[0]
    //最大累加和
    sum := dp[0]
    //开始逐步计算1-n个位置，子数组的最大累加和
    for i := 1; i < len(arr); i ++ {
        dp[i] = max(0, dp[i-1]) + arr[i]
        sum = max(sum, dp[i])
    }
    return sum
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

解法二

空间复杂度为O(1)的方式。
算法的基本思路：

• 即然能够定义一个临时数组存储取最大值，那么可以定义一个哨兵岗位存储最大累加和maxsum
• 然后每迭代一步的位置i，最大累加和需要存储i_sum表示，下一步i+1位置迭代就可以判断是否字节取arr[i+1]还是跟i_sum相加

/**
 * max sum of the subarray
 * @param arr int整型一维数组 the array
 * @return int整型
*/
func maxsumofSubarray( arr []int ) int {
    // write code here
    //边界条件处理
    if len(arr) == 0 {
        return 0
    }
    /*
      状态转移的思路（或子问题的思路）
      与数组第i个位置arr[i]相加后，取前面i-1的子数组中求和最大值
      最关键的最大值求法：max(0, dp[i-1])
       - 与0比较，是因为一旦第i-1个位置的最大和是负数
       - 负数与arr[i]会导致和更小
    */

    //定义一个一维的数组，每个位置存到i位置的最大累加和
    dp := make([]int, len(arr))
    //第0个位置初始化
    dp[0] = arr[0]
    //最大累加和
    sum := dp[0]
    //开始逐步计算1-n个位置，子数组的最大累加和
    for i := 1; i < len(arr); i ++ {
        dp[i] = max(0, dp[i-1]) + arr[i]
        sum = max(sum, dp[i])
    }
    return sum
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}