最大子数组の求救

[风速法师]

有没有大佬可以教教我最大子数组里的思路

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

用动态规划（dp

[风速法师]

怎么动规dp
后半段好做可前半段+x-x的怎么做

[风速法师]

话说我们加个好友

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

好友是什么？信友队有这东西吗？还是我孤陋寡闻了？

[风速法师]

呵呵

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

什么意思？要我干嘛？

[风速法师]

你看右上角

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

[风速法师]

我们还是关注这题把
问一下前半段怎么做

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

先想出状态转移方程

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

这不就最大子段和吗？

#include<bits/stdc++.h>
2
using namespace std;
3
int n,a[114514],dp[114514];
4
int main(){
5
    scanf("%d", &n);
6
    for(int i=1;i<=n;i++){
7
        scanf("%d", &a[i]);
8
    }
9
    dp[1]=a[1]; 
10
    for(int i=2;i<=n;i++){
11
        dp[i]=max(dp[i-1]+a[i],a[i]);
12
    }
13
    sort(dp+1,dp+1+n);
14
    printf("%d",dp[n]);
15
    return 0;
16
} 
} 

[风速法师]

不会吧，我们不在讲同一道

最大子数组



时间限制：2 s；内存限制：512 MB。



给定一个由 n个整数组成的数组 a1,a2,...,an。同时给定两个整数 k 和 x。你需要执行以下操作：将 x 加到恰好 k 个不同的位置的元素上，并从其他元素中减去 x。



例如，如果 a=[2,−1,2,3]，k=1，x=2，我们选择第一个元素，那么操作后数组 a=[4,−3,0,1]。



设 f(a) 表示 a 的子数组的最大可能和。a 的子数组是 a 的一部分连续元素组成的 ai,ai+1,...,aj，其中 1≤i≤j≤n。空的子数组也应该被考虑在内，它的和为 0。



设 a′ 是应用上述操作后的数组 a。按照最大可能的方式进行操作，使得 f(a′) 的值最大，并打印 f(a′) 的最大可能值。



输入格式



第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。



每个测试用例的第一行包含三个整数 n、k、x (1≤n≤2×105，0≤k≤min(20,n)，−109≤x≤109)。



第二行包含 n 个整数 a1,a2,...,an (−109≤ai≤109)。



所有测试用例中 n 的总和不超过 2×105。



输出格式



对于每个测试用例，输出一个整数，表示 f(a′) 的最大可能值。



样例输入



4

4 1 2

2 -1 2 3

2 2 3

-1 2

3 0 5

3 2 4

6 2 -8

4 -1 9 -3 7 -8



样例输出



5

7

0

44

[风速法师]

不考虑+x-x的我写出来了

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+5;
int dp[maxn]; 
int n,k,x,a[maxn];
int res=0;
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>k>>x;
		res=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			dp[i]=max(dp[i-1],dp[i-1]+a[i]);
			res=max(dp[i],res);
		}
		cout<<res;
	}
	
	return 0;
}

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

取max还不考虑？

[风速法师]

此话怎讲

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

666，一个数加上负数，那么这个值肯定小于原数

[风速法师]

好像没错

[风速法师]

但最大子段和可以分离啊
最大子数组不能啊

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

抱歉，我没看过题面，但是我在网上搜出来的最大子数组是类似与最大子段和的