2023-07-20力扣今日二题-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-07-20力扣今日二题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接：

53. 最大子数组和

题意：

长度n的数组，求和最大的一段数组，返回最大和

解：

核心思路：设置一个下标L，遍历数组，如果[L,R]小于0，代表保留这一段是累赘，直接丢弃掉，将L设为R+1，这样就是一个滑动窗口的做法，但是如果用下标来表示区间，就需要前缀和

优化：直接不需要前缀和，在遍历的时候叠加就行，如果是求最大的一段数组，那么这个前缀sum小于0时，就是累赘，直接让sum=0相当于抛弃

实际代码：

优化后：

#include<bits/stdc++.h>
using namespace std;
const int Nmax=1E5+7;
int maxSubArray(vector<int>& nums)
{
    int Max=INT_MIN,lg=nums.size(),sum=0;
    if(lg==1) return nums[0];
    
    for(int i=0;i<lg;i++)
    {
        sum+=nums[i];
        Max=max(Max,sum);
        if(sum<0) sum=0;
    }
    return Max;
}
int main()
{
    vector<int> nums;int temp;
    while(cin>>temp)
    {
        nums.push_back(temp);
    }
    int ans=maxSubArray(nums);
    cout<<ans<<endl;
    return 0;
}

优化前：

#include<bits/stdc++.h>
using namespace std;
const int Nmax=1E5+7;
int maxSubArray(vector<int>& nums)
{
    int Max=nums[0],left_Max=0,right_Max=0,zt_Max=0;
    
    int lg=nums.size();
    if(lg==1) return nums[0];
    vector<int>sum(lg,nums[0]);//前缀和 
    for(int i=1;i<lg;i++)
    {
        sum[i]=sum[i-1]+nums[i];
        Max=max(Max,nums[i]);
    }
    
    for(int i=0;i<lg;i++)
    {
        //找最大 正数开始
        if(zt_Max==0 && nums[i]>0)
        {
            left_Max=i;zt_Max=1;//正序列 
        }
        if(zt_Max==1 && nums[i]<0)//结尾正序列 -> 转负 
        {
            Max=max(Max,sum[i-1]-(left_Max?sum[left_Max-1]:0) );//更新最大值 
            zt_Max=-1;
        }
        if(zt_Max==-1 && nums[i]>0)//结尾负序列 -> 转正 
        {
            if( sum[i-1]-(left_Max?sum[left_Max-1]:0)<0 )//前一段产出负值 -> 抛弃 
            {
                left_Max=i;
            }
            zt_Max=1;
        }
    }
    if(zt_Max!=0 && left_Max!=lg-1) Max=max(Max,sum[lg-1]-(left_Max?sum[left_Max-1]:0) );
    return Max;
}
int main()
{
    vector<int> nums;int temp;
    while(cin>>temp)
    {
        nums.push_back(temp);
    }
    int ans=maxSubArray(nums);
    cout<<ans<<endl;
    return 0;
}

限制：文章来源地址https://www.toymoban.com/news/detail-604277.html