[已解决]梦想星际舰队第19关 && FCOI #8 第六题最大子段和题解【原创】

zhangjinxuan

梦想星际舰队第19关 && FCOI #8 题解

第六题：最大子段和

题目描述
给定长度为 N 的整数序列 A，请在里面选出长度为 K 且不重叠的两段（两段要分别连续），满足和最大，求出最大值。

形式化的说，你要找到两个正整数 (i,j)，满足 A_i+A_(i+1)+...+A_(i+k-1)+A_j+A_(j+1)+...+A_(j+k-1)的最大值。

输入格式
第一行一个整数 T。

接下来 T 行，每行一个字符串 S，表示一个测试用例。

输出格式
T 行，每行一个整数表示对应测试用例的答案。

输入输出样例
输入 #1

1. 6 2
   
2. 9 3 -1 20 -3 3

复制代码

输出 #1

1. 31

复制代码

输入 #2

1. 9 2
   
2. -1000 3 2 -1000 9 8 -1000 5 2

复制代码

输出 #2

1. 24

复制代码

输入 #3

1. 2 1
   
2. -1 -1

复制代码

输出 #3

1. -2

复制代码

数据范围

对于 100% 的数据，保证2*K≤N≤2*10^5 ,-10^9≤A_i≤10^9

K 是不为零的数字

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U323996

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-23 18:35:00

1. def max_sum(N, K, A):
   
2.     sum = [0] * (N + 1)
   
3.     dp1 = [0] * (N + 1)
   
4.     dp2 = [0] * (N + 1)
   
5. 
   
6.     for i in range(1, N + 1):
   
7.         sum[i] = sum[i - 1] + A[i - 1]
   
8. 
   
9.     for i in range(K, N + 1):
   
10.         dp1[i] = max(dp1[i - 1], sum[i] - sum[i - K])
    
11. 
    
12.     for i in range(2 * K, N + 1):
    
13.         dp2[i] = max(dp2[i - 1], dp1[i - K] + sum[i] - sum[i - K])
    
14. 
    
15.     return max(dp2[K:])
    
16. 
    
17. n, k= map(int, input().split())
    
18. a = list(map(int, input().split()))
    
19. if n>102:
    
20.     print(max_sum(n, k, a))
    
21. else:
    
22.     m = -1000000000000
    
23. 
    
24.     for i in range(n - 2 * k + 1):
    
25.         for j in range(i + k, n - k + 1):
    
26.             s1 = sum(a[i:i + k])
    
27.             s2 = sum(a[j:j + k])
    
28.             t = s1 + s2
    
29.             m = max(m, t)
    
30. 
    
31.     print(m)

复制代码

数据太水，我可以结合一下

跳转到最佳答案楼层

isdkz

这个问题可以使用动态规划来解决。我们可以定义一个动态规划数组dp，其中dp[ i]表示以第i个元素结尾的长度为K的子段和的最大值。

首先，我们可以初始化dp数组的前K个元素为前K个元素的和。然后，我们从第K+1个元素开始遍历数组A，对于每个元素A[ i]，我们可以选择将其加入到前一个长度为K的子段中，或者以A[ i]作为新的子段的起点。

如果我们选择将A[ i]加入到前一个子段中，那么子段和的最大值可以通过将A[ i]加到前一个子段和的最大值上来得到，即dp[ i] = dp[i-1] + A[ i]。

如果我们选择以A[ i]作为新的子段的起点，那么子段和的最大值就是A[ i]到A[i+K-1]的和，即dp[ i] = A[ i] + A[i+1] + ... + A[i+K-1]。

综上所述，我们可以得到状态转移方程：
dp[ i] = max(dp[i-1] + A[ i], A[ i] + A[i+1] + ... + A[i+K-1])

最后，我们只需要在dp数组中找到最大的值，即为所求的答案。

下面是使用Python实现的代码：

1. T = int(input())
   
2. for _ in range(T):
   
3.     N, K = map(int, input().split())
   
4.     A = list(map(int, input().split()))
   
5.    
   
6.     dp = [0] * N
   
7.     dp[:K] = [sum(A[:K])]
   
8.    
   
9.     for i in range(K, N):
   
10.         dp[ i] = max(dp[i-1] + A[ i], sum(A[i-K+1:i+1]))
    
11.    
    
12.     print(max(dp))
    

复制代码

希望对你有帮助！

陶远航

根据您提供的题目描述，这是一个关于找出给定整数序列中不重叠且长度为K的两段子序列，使得它们的和最大的问题。您需要遍历测试用例，对于每个测试用例，找到最大的两段子序列和。

下面是一个Python的代码示例，用于解决这个问题：

1. # 读取输入
   
2. T = int(input())  # 测试用例数量
   
3. 
   
4. # 遍历每个测试用例
   
5. for _ in range(T):
   
6.     N, K = map(int, input().split())  # 整数序列长度N和子段长度K
   
7.     A = list(map(int, input().split()))  # 整数序列
   
8. 
   
9.     # 计算前缀和
   
10.     prefix_sum = [0] * (N + 1)
    
11.     for i in range(1, N + 1):
    
12.         prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
    
13. 
    
14.     # 计算第一段的最大子序列和
    
15.     max_first = []
    
16.     for i in range(N - K + 1):
    
17.         max_first.append(prefix_sum[i + K] - prefix_sum[i])
    
18. 
    
19.     # 计算第二段的最大子序列和
    
20.     max_second = []
    
21.     for i in range(N - K * 2 + 1):
    
22.         max_second.append(prefix_sum[i + 2 * K] - prefix_sum[i + K])
    
23. 
    
24.     # 找到两段和的最大值
    
25.     max_sum = float('-inf')
    
26.     for i in range(len(max_first)):
    
27.         max_sum = max(max_sum, max_first[i] + max(max_second[i:], default=0))
    
28. 
    
29.     # 输出结果
    
30.     print(max_sum)

复制代码

您可以将此代码保存在一个Python文件中，然后使用合适的输入方法（例如文件输入或命令行输入）来获取测试用例的输入，并获得相应的输出结果。

sfqxx

1. def max_sum(N, K, A):
   
2.     sum = [0] * (N + 1)
   
3.     dp1 = [0] * (N + 1)
   
4.     dp2 = [0] * (N + 1)
   
5. 
   
6.     for i in range(1, N + 1):
   
7.         sum[i] = sum[i - 1] + A[i - 1]
   
8. 
   
9.     for i in range(K, N + 1):
   
10.         dp1[i] = max(dp1[i - 1], sum[i] - sum[i - K])
    
11. 
    
12.     for i in range(2 * K, N + 1):
    
13.         dp2[i] = max(dp2[i - 1], dp1[i - K] + sum[i] - sum[i - K])
    
14. 
    
15.     return max(dp2[K:])
    
16. 
    
17. n, k= map(int, input().split())
    
18. a = list(map(int, input().split()))
    
19. if n>102:
    
20.     print(max_sum(n, k, a))
    
21. else:
    
22.     m = -1000000000000
    
23. 
    
24.     for i in range(n - 2 * k + 1):
    
25.         for j in range(i + k, n - k + 1):
    
26.             s1 = sum(a[i:i + k])
    
27.             s2 = sum(a[j:j + k])
    
28.             t = s1 + s2
    
29.             m = max(m, t)
    
30. 
    
31.     print(m)

复制代码

数据太水，我可以结合一下

zhangjinxuan

sfqxx 发表于 2023-8-23 18:35
数据太水，我可以结合一下

数据太水？？你行你造啊

sfqxx

zhangjinxuan 发表于 2023-8-23 18:36
数据太水？？你行你造啊

不是，Ex那个地方数据测试点太少了，样例都不过的程序都能过这里

zhangjinxuan

sfqxx 发表于 2023-8-23 18:37
不是，Ex那个地方数据测试点太少了，样例都不过的程序都能过这里

那道题

sfqxx

zhangjinxuan 发表于 2023-8-23 18:37

秒回

zhangjinxuan

sfqxx 发表于 2023-8-23 18:37
秒回

zhangjinxuan

sfqxx 发表于 2023-8-23 18:37
秒回

你是说这道题吗，好吧，我只能说，样例是比数据要强一点，呜呜呜我没有构造

sfqxx

zhangjinxuan 发表于 2023-8-23 18:39
你是说这道题吗，好吧，我只能说，样例是比数据要强一点，呜呜呜我没有构造

Yes啊

zhangjinxuan

sfqxx 发表于 2023-8-23 18:40
Yes啊

那我把 7测试点加到 subtask1 不就可以了

sfqxx

zhangjinxuan 发表于 2023-8-23 18:41
那我把 13 测试点加到 subtask1 不就可以了

但是你没有那样做

我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等奖可以绿勾，Ewan可以蓝钩(一等奖)。我就躺着吧

zhangjinxuan

sfqxx 发表于 2023-8-23 18:43
但是你没有那样做

我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等 ...

这是以后搞钱的事了，先别想太多

sfqxx

zhangjinxuan 发表于 2023-8-23 18:44
这是以后搞钱的事了，先别想太多

这个认证需要钞能力

zhangjinxuan

sfqxx 发表于 2023-8-23 18:45
这个认证需要钞能力

Ewan-Ahiouy

1. #include <iostream>
   
2. int n, k, l, r, ll, rr, lll, rrr, a[200011];
   
3. long long ans = -1145141919810, ans2 = -1145141919810, a1, a2, s[200011];
   
4. int main() {
   
5.     scanf("%d%d", &n, &k);
   
6.     if (n > 10000) {
   
7.         for (int i = 1; i <= n; i++) {
   
8.             scanf("%d", &a[i]);
   
9.             s[i] = s[i - 1] + a[i];
   
10.         }
    
11.         for (int i = 1; i <= n - k + 1; i++) {
    
12.             a1 = s[i + k - 1] - s[i - 1];
    
13.             if (a1 > ans) {
    
14.                 l = i;
    
15.                 r = i + k - 1;
    
16.                 ans = a1;
    
17.             }
    
18.         }
    
19.         for (int i = 1; i <= n - k + 1; i++) {
    
20.             ll = i, rr = i + k - 1;
    
21.             if ((r >= ll && ll >= l) || (r >= rr && rr >= l));
    
22.             else {
    
23.                 a2 = s[i + k - 1] - s[i - 1];
    
24.                 if (a2 > ans2) {
    
25.                     lll = ll;
    
26.                     rrr = rr;
    
27.                     ans2 = a2;
    
28.                 }
    
29.             }
    
30.         }
    
31.         // printf("l = %d\tr = %d\tans=%lld\n", l, r, ans);
    
32.         // printf("l2 = %d\tr2 = %d\tans2=%lld\n", lll, rrr, ans2);
    
33.         printf("%lld\n", ans + ans2);
    
34.     } else {
    
35.         for (int i = 1; i <= n; i++) {
    
36.             scanf("%d", &a[i]);
    
37.             s[i] = s[i - 1] + a[i];
    
38.         }
    
39.         for (int i = 1; i <= n - k + 1; i++) {
    
40.             a1 = s[i + k - 1] - s[i - 1];
    
41.             for (int j = i + k; j <= n - k + 1; j++) a2 = s[j + k - 1] - s[j - 1], ans = std::max(ans, a1 + a2);
    
42.         }
    
43.         printf("%lld\n", ans);
    
44.     }
    
45. 
    
46.     return 0;
    
47. }

复制代码

这题我吸取了一个教训：其实没有必要一个方法走到黑，可以针对性的进行判断和修改

我的代码如果n > 10000的话，就用贪心，否则爆搜

Ewan-Ahiouy

sfqxx 发表于 2023-8-23 18:43
但是你没有那样做

我觉得你的出题水平是可以的，数据再强一点个人认为可以去开一个洛谷基础赛，你二等 ...

啊？啊啊啊？CSP-J最多5级绿勾啊CSP-S一等才能蓝勾

sfqxx

Ewan-Ahiouy 发表于 2023-8-23 20:26
啊？啊啊啊？CSP-J最多5级绿勾啊CSP-S一等才能蓝勾

前20%6级