最大连续子序列和

算法与数据结构

目录

  1. 描述
  2. 代码1：
  3. 解释1：
  4. 代码2:
  5. 解释2（动态规划）：

描述

给定一个数字序列$A_1,A_2,…,A_n,求i,j(1\le i \le j\le n)$,使得$A_i+…+A_j$最大并输出最大值

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun maxSubArray(nums: IntArray): Int {
    var sum = 0
    var maxSum = Int.MIN_VALUE
    for(i in nums){
        sum += i
        if (sum > maxSum){
            maxSum = sum
        }
        if (sum < 0){
            sum = 0 
        }
    }
    return maxSum
}

解释1：

1. 假设A[0]>0,A[0]+A[1]+…+A[p-1]>0，A[0]+A[1]+…+ A[p-1]+ A[p]<0,p是数组的元素累加和过程中遇到的第一个小于零的位置.

那么对于k属于[0,p-1], 可推导出A[0]+…+A[k]>A[s]+…+A[k],其中$s\in(0,k]$,这说明0~k位置的元素累加和大于任意s~k位置的子序列之和,所以在[0,p-1]区间累加求和并记录最大值.

2. 最大连续子序列不可能包含p,因为A[n]+…+A[p]+A[p+1]+…+A[m]中A[n]+…A[p]<0，所以A[p+1]+…+A[m]大于A[n]+…+A[p]+…+A[m], 则说明A[n]+…+A[p]+…+A[m]不是最大连续子序列.

3. 所以从p+1起,重新累加求合并记录最大值

代码2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fun maxSubArray(nums: IntArray): Int {
    var sum = 0
    var maxSum = Int.MIN_VALUE
    nums.forEachIndexed{ i, v ->
        when(i){
            0 -> sum = v
            else -> {
                sum = Math.max(sum+v ,v)
            }
        }
        if (sum > maxSum){
            maxSum = sum
        }
    }
    return maxSum
}

解释2（动态规划）：

令状态 dp[i] 表示以 A[i] 作为末尾的连续序列的最大和.因为 dp[i] 要求是必须以 A[i] 结尾的连续序列，那么只有两种情况:

  1. 这个最大和的连续序列只有一个元素,即以 A[i] 开始,以 A[i] 结尾.
  2. 这个最大和的连续序列有多个元素,即从前面某处 A[p] 开始 (p<i),一直到 A[i] 结尾

状态转移方程: dp[i] = max{ A[i], dp[i-1]+A[i] }

边界: dp[0] = A[0]