文章
14
粉丝
230
获赞
26
访问
69.9k
跟之前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;
}
}
...
登录后发布评论
暂无评论,来抢沙发