洛谷 1115. 分治/贪心 例题
原题链接
简单
作者:
kxzz
,
2022-06-23 17:00:53
,
所有人可见
,
阅读 149
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N], b[N];
int main()
{
//贪心解法
int n; cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
int res = -2e9;
for (int i = 0; i < n; i++)
{
if (i == 0)b[i] = a[i];//只有一个数就加到集合中去即可
else b[i] = max(a[i], b[i - 1] + a[i]);//如果集合加上这个数会更优就加,否则舍弃集合(连续的子串)
res = max(res, b[i]);//每次与集合中的元素取最大值
}
cout << res << endl;
return 0;
}
//分治解法
//给定区间l~r,取其中点为mid
//有三种情况:
//1、l < i < mid < j < r
//2、l < i < j < mid
//3、mid < i < j < r
#include<iostream>
#include<cmath>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int Merge(int l, int r)
{
if (l == r)return a[l];
int mid = l + r >> 1;
int sum = 0, res1 = -2e9, res2 = -2e9;
for (int i = mid;i >= l;i--)
{
sum += a[i];
res1 = max(res1, sum);
}
sum = 0;
for (int i = mid + 1; i <= r; i++)
{
sum += a[i];
res2 = max(res2, sum);
}
return max(max(Merge(l, mid), Merge(mid + 1, r)), res1 + res2);
}
int main()
{
int n; cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
cout << Merge(0, n - 1) << endl;
return 0;
}