最大子段和
题目描述
给出一个长度为 n 的序列 $a$，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 $n$。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 $a_i$。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
7
2 -4 3 -1 2 -4 3
样例输出 #1
4
提示
样例 1 解释
选取 [3, 5] 子段 ${3, -1, 2}$，其和为 $4$。
数据规模与约定
- 对于 40\% 的数据，保证 $n \leq 2 \times 10^3$。
- 对于 100\% 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。
这是我的代码
#include <iostream>
#include <limits.h>
#include <cmath>
using std::cin;
using std::cout;
int a[200010];
int n;
int max(int x,int y)
{
using std::max;
return max(x,y);
}
int find_max_crossing(int l,int r,int mid)
{
int left_sum=INT_MIN , right_sum=INT_MIN;
int tmp_sum=0;
for (int i=mid;i>=l;i--)
{
tmp_sum+=a[i];
if (tmp_sum>left_sum)
left_sum=tmp_sum;
}
tmp_sum=0;
for (int i=mid;i<=r;i++)
{
tmp_sum+=a[i];
if (tmp_sum>right_sum)
{
right_sum=tmp_sum;
}
}
return (left_sum+right_sum);
}
int find_max(int l,int r)
{
if (l==r)
{
return a[l];
}
else
{
int mid=(l+r)/2;
int a=find_max(l,mid);
int b=find_max(mid+1,r);
int c=find_max_crossing(l,r,mid);
return max(a,max(b,c));
}
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
cout<<find_max(1,n);
return 0;
}
// output : 6