【DP】大厂真题：小红书2023秋招提前批-连续子数组最大和

题目描述与示例

题目描述

小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？

输入描述

第一行输入一个正整数t，代表询问次数。

对于每次询问，输入两行：

第一行输入两个整数n和x。代表数组的大小，以及小红可以修改成的元素。

第二行输入n个正整数a_i，代表小红每次询问拿到的数组。

1 ≤ t ≤ 100000
1 ≤ n ≤ 200000
-10^9 ≤ x, a_i ≤ 10^9
1
2
3

每组所有询问的n的和不超过200000。

输出描述

输出t行，每行输出一个整数，代表每次询问能够得到的连续子数组的最大和。

示例

输入

3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1
1
2
3
4
5
6
7

输出

15
-2
15
1
2
3

说明

第一组询问，修改第二个数。

第二组询问，不进行任何修改。

第三组询问，修改第三个数。

时空限制

时间限制：3s

内存限制：512MB

解题思路

注意，本题的部分逻辑和LeetCode53. 最大子数组和 完全一致，属于本题的一道延申题。而修改的操作，可以类比股票问题的做法。

代码

Python

# 题目：【DP】小红书2023秋招提前批-连续子数组最大和
# 作者：闭着眼睛学数理化
# 算法：DP/前缀和
# 相关题目：LC53. 最大子数组和
# 代码有看不懂的地方请直接在群上提问


# 用dp解决问题的函数
def sol(nums, n, x):
    # dp[i]表示以nums[i]为结尾的子数组，能够取得的最大连续子数组和的情况
    # dp[i][0]表示尚未进行修改，能取得的最大子数组和
    # dp[i][1]表示已经进行修改，能取得的最大子数组和
    dp = [[0, 0] for _ in range(n)]
    # 初始化dp数组
    dp[0] = [nums[0], x]
    # 初始化答案
    ans = max(dp[0])
    for i in range(1, n):
        # 考虑尚未进行过修改的情况，即考虑dp[i][0]的动态转移方程
        # 注意此处和 LC53. 最大子数组和 的逻辑是完全一致的
        # 如果dp[i-1][0]是负数，那么dp[i][0]则不再考虑dp[i-1][0]，仅包含nums[i]即可
        # 如果dp[i-1][0]是正数，那么dp[i][0]则需要考虑dp[i-1][0]，要同时包含nums[i]和dp[i-1][0]
        if dp[i-1][0] < 0:
            dp[i][0] = nums[i]
        else:
            dp[i][0] = nums[i] + dp[i-1][0]
        # 考虑已经进行过修改的情况，即考虑dp[i][1]的动态转移方程
        # 有两种修改情况：
        # 在i位置进行修改，得到的最大连续子数组和是         dp[i-1][0] + x
        # 在i之前的某个位置进行修改，得到的最大连续子数组和是 dp[i-1][1] + nums[i]
        dp[i][1] = max(dp[i-1][0]+x, dp[i-1][1]+nums[i])
        # 更新答案
        ans = max(ans, max(dp[i]))
    return ans


t = int(input())
# 遍历t次，表示t次询问
for _ in range(t):
    # 获得本次询问的数组长度n和可以修改数字x
    n, x = map(int, input().split())
    # 输入本次询问的数组
    nums = list(map(int, input().split()))
    print(sol(nums, n, x))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

时空复杂度

时间复杂度：O(N)。需要一次遍历原数组。

空间复杂度：O(N)。dp数组所占空间，如果使用滚动dp数组，空间复杂度可以降到O(1)。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多