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

子数组的最大累加和问题

http://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd

解题思路

一般求子数组的最大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
}
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务