核心思路是定位截取数组从哪里开始，哪里结束。前缀和稍微想想是个sum[i]-sum[j]的问题。对于任意i而言，sum[j]越小越好。按这个贪心逻辑走下去，fusum维护一个最小的sum[j]。然后我们用一个sum记录a[1]到a[i]之和。
然后就ac了


题目的执行用时击败了99%的用户

时间刺客

题目的内存消耗击败了99%的用户

空间掌握者

#include<iostream>
using namespace std;
int main()
{
    int n,ans=-1e9,sum=0,fumax=-0;
    cin>>n;
    for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            sum+=temp;
            int fusum=-sum;
            if(sum+fumax>ans)ans=sum+fumax;
            if(fusum>fumax)fumax=fusum;
            
        }
    cout<<ans;
}

最大子段和

这道题不是摁贪心么，数组都不需要的

#include<iostream>
using namespace std;
int main()
{
int n,ans=-1e9,sum=0,fumax=-0;
cin>>n;
for(int i=0;i<n;i++)
{
int t

全部评论 1