Maximum Sum(贪心策略,模运算,最大子段和)

题目描述

你有一个由 $n$ 个整数组成的数组 $a$ 。

你要对它进行 $k$ 次操作。其中一个操作是选择数组 $a$ 的任意连续子数组(可能为空)，并在数组的任意位置插入该子数组的和。

你的任务是找出 $k$ 次这样的操作后数组可能的最大和。

由于这个数字可能非常大，请输出取模为 $10^9+7$ 的答案。

提示：数字 $x\mathrm{mod}p$ 的余数等于最小非负数 $y$，满足 $x=p\cdot q+y$ ($q$ 为整数)。

输入格式

第一行包含两个整数 $n$ 和 $k(1\le n,k\le 2\ast 10^5)$—分别是数组的长度 $a$ 和操作次数。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(-10^9\le a_i\le 10^9)$。

输出格式

输出一个整数—经过 $k$ 次运算模数 $10^9+7$ 后得到的数组最大和。

样例输入1

2 2
-4 -7

样例输出1

999999996

样例输入2

3 3
2 2 8

样例输出2

96

提交链接

https://hydro.ac/d/lp728/p/13

提示

样例解释 $1$:
在第一个测试用例中，最好在数组中取一个空子数组两次，并在任意位置插入空子数组的和$(0)$，这样得到的数组和为 $(-4)+(-7)+0+0=-11$，模数 $10^9+7$ 为 $999999996$。

解析

核心：找到数组中总和最大的子数组。

设 $s$ 表示为原始数组的总和，$x$ 表示为原始数组中总和最大的子数组的总和。
$k=1$ 时，答案为 $s+x$；$k=2$ 时，答案为 $s+x+2\ast x$

任意 $k$ ，具有最大和的子数组的和最初是 $x$ ，然后是 $2\cdot x$ ，然后是 $4\cdot x$ ， … ， $2^{k-1}\cdot x$
答案等于 $s+x+2\cdot x+\cdots +2^{k-1}\cdot x=s+2^k\cdot x-x$。

取余的时候要考虑负数的情况。若为负数可以先加上模数再进行取余。

参考代码

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 9 , mod = 1e9 + 7;
typedef long long ll;
int t , n , a[maxn] , k;
int main()
{ll ans = 0;cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];ans += a[i];}ans = (ans % mod + mod) % mod;ll sum = 0 , mx = 0;for(int i = 1; i <= n; i++)  //区间最大和{sum += a[i];if(sum < 0)sum = 0;mx = max(mx , sum);}mx %= mod;ll two = 1;for(int i = 1; i <= k; i++)two = two * 2 % mod;ans = (ans + two * mx - mx + mod) % mod;cout << ans << endl;return 0;
}