思路
-
固定三个点,左节点,右节点和一个虚拟结点,记录下标,让虚拟结点不断往右跑,尺取法的思想
-
DP,由于DP和尺取时间复杂度一样,这里就不放代码了
注意
特判全是负数的情况,如果全部元素都是负数,则输出 0 第一个元素值 最后一个元素值
如果不在最后特判的话,如果全是负数则错误,比如:
5
-1 -1 -1 -1 -1
就会输出错误答案:
0 -1 -1
AC代码
#include<iostream>
#include<algorithm>
#include<map>
#include<string.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f;
int a[10010];
int main()
{
int n,cnt=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]<0) cnt++;
}
if(cnt==n)
{
cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
return 0;
}
int l=0,r=0,l1=0,sum=0,ma=a[0]; // ma=0 + 下面if语句两行掉一下顺序在pta会错一组数据,ma必须为a[0],下面if条件顺序必须这样写,否则其他地方需要变一下
for(int i=0;i<n;i++)
{
sum+=a[i];
if(sum>ma) ma=sum,l=l1,r=i; // 条件不是sun>=0 更新l、r
if(sum<0) sum=0,l1=i+1; // 让l1先去往右跑
// if(sum>ma) ma=sum,l=l1,r=i; // 条件不是sun>=0 更新l、r
}
cout<<ma<<" "<<a[l]<<" "<<a[r]<<endl; // 输出最大值、左值、右值
return 0;
}