摘要
Title: 1051. 最大的和
Tag: dp、最大子段和
Memory Limit: 64 MB
Time Limit: 1000 ms

1051. 最大的和

题意

对于给定的整数序列 A={a1,a2,…,an}，找出两个不重合连续子段，使得两子段中所有数字的和最大。
思路

首先是最大子段和的dp证明

最后求出来的dp[i]是以i为结尾的所有连续子序列的和的最大值，而我们要统计整个数组的连续子序列最大值，所以要求 $\max_{i=0}^{n}dp[i]$

回到本题
运用前后缀分解的思想，由于要两段，所以一定存在一个分界点k可以将两段分开
所以我们需枚举所有的分界点k，求1到k的最大子段和和k+1到n的最大子段和的加和的最大值即可

代码

'''
Author: NEFU AB-IN
Date: 2023-03-23 21:42:54
FilePath: \Acwing\1051\1051.py
LastEditTime: 2023-03-23 21:54:54
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(5e4 + 10)
INF = int(2e9)

dp, g, h, w = [0] * N, [0] * N, [0] * N, [0] * N

for _ in range(int(input())):
    n = int(input())
    w[1:] = list(read())

    # s = -INF
    dp[0] = g[0] = -INF  # 这里设成负无穷 是因为每一段都不能是空的，无解就设成-INF
    for i in range(1, n + 1):
        dp[i] = w[i] + max(0, dp[i - 1])
        # s = max(0, s) + w[i]
        g[i] = max(dp[i], g[i - 1])
        # g[i] = max(s, g[i - 1])

    # s = -INF
    dp[n + 1] = h[n + 1] = -INF
    for i in range(n, 0, -1):
        dp[i] = w[i] + max(0, dp[i + 1])
        # s = max(0, s) + w[i]
        h[i] = max(dp[i], h[i + 1])
        # h[i] = max(s, h[i + 1])

    res = -INF
    for i in range(1, n + 1):
        res = max(res, g[i] + h[i + 1])
    print(res)

优化版本

'''
Author: NEFU AB-IN
Date: 2023-03-23 21:42:54
FilePath: \Acwing\1051\1051.py
LastEditTime: 2023-03-23 21:52:59
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(5e4 + 10)
INF = int(2e9)

dp, g, h, w = [0] * N, [0] * N, [0] * N, [0] * N

for _ in range(int(input())):
    n = int(input())
    w[1:] = list(read())

    s = -INF
    dp[0] = g[0] = -INF  # 这里设成负无穷 是因为每一段都不能是空的，无解就设成-INF
    for i in range(1, n + 1):
        s = max(0, s) + w[i]
        g[i] = max(s, g[i - 1])
    s = -INF
    dp[n + 1] = h[n + 1] = -INF
    for i in range(n, 0, -1):
        s = max(0, s) + w[i]
        h[i] = max(s, h[i + 1])

    res = -INF
    for i in range(1, n + 1):
        res = max(res, g[i] + h[i + 1])
    print(res)

1051. 最大的和

题意

思路

代码