文章

14

粉丝

230

获赞

26

访问

70.3k

头像
记录下标
P1334 浙江大学/中国矿业大学机试题
发布于2022年8月21日 11:15
阅读数 4.5k

跟之前dp[i]=max(dp[i-1]+aa[i],a[i])不一样的是需要记录首尾下标

首下标改变:dp[i-1]+aa[i]<a[i],记录当前的首下标

首、尾下标更新:当前dp值大于最大值,需要更新最大值的同时,更新首、尾下标,

首下标,即当前记录的首下标,

尾下标,即当前遍历的下标;

#include<bits/stdc++.h>

using namespace std;

int aa[10001];
int dp[10001];
int maxx;

int main()
{
    int num;
    while(cin>>num)
    {
        if(num==0) break;
        memset(aa,0,sizeof(aa));
        memset(dp,0,sizeof(dp));
        int left=0,right=0,left1=0;
        cin>>aa[0];
        maxx=aa[0];
        dp[0]=aa[0];
        for(int i=1; i<num; i++)
        {
            cin>>aa[i];
            int temp=dp[i-1]+aa[i];
            if(temp>=aa[i])
                dp[i]=temp;
            else
            {
                dp[i]=aa[i];
                left1=i;
            }
            if(maxx<dp[i]) //maxx刷新的同时更新左右下标
            {
                maxx=dp[i];
                right=i;
                left=left1;
            }

        }
     ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发