为了账号安全,请及时绑定邮箱和手机立即绑定

给定一个数组和一个正整数N,求一个和小于N的最长连续子数组

给定一个数组和一个正整数N,求一个和小于N的最长连续子数组

泛舟湖上清波郎朗 2019-08-09 23:22:40
给定一个数组和一个正整数N,求一个和小于N的最长连续子数组头条算法题相关代码//请把代码文本粘贴到下方(请勿用图片代替代码)大神!!!思路,代码,注释
查看完整描述

2 回答

?
千万里不及你

TA贡献1784条经验 获得超9个赞

可以用动态规划的思想去看,
设S(i)为以第i个元素结尾的和小于N的最长连续数组设len(i)为S(i)的长度设sum(i)为S(i)的和
边界:
len(0)=arr[0]sum(0)=arr[0](对于不可取的数(比N大)我们也把和记上)
当计算S(i)时,如果arr[i]>=N,那么舍弃
否则
将arr[i]加入S(i)中(目前len(i)为1,sum(i)为arr[i])
不停归并S(i)左边相邻的S(i-len(i)),直到sum(i)不再小于N
这里需要注意对于一些比N大的项原来不可取,现在也有可能取到
最后从S(i)最左的元素往右筛除,缩小数组直到总和小于N
最后根据最长的len返回数组即可
functionlsa(arr,n){
if(arr.length<=0){return[]}
//1
constlen=[arr[0]constsum=[arr[0]]
for(leti=1;iif(arr[i]>=n){//2
len[i]=0
sum[i]=arr[i]
}else{//3
//3.1
len[i]=1
sum[i]=arr[i]
//3.2
for(letj=i-len[i];j>=0&&sum[i]sum[i]+=sum[j]
len[i]+=len[j]||1//3.2.1
}
//3.3
for(letj=i+1-len[i];j=n;j++){
len[i]-=1
sum[i]-=arr[j]
}
}
}
constmax=len.reduce((max,l,i)=>l>len[max]?i:max,0)
returnarr.slice(max+1-len[max],max+1)
}
                            
查看完整回答
反对 回复 2019-08-09
  • 2 回答
  • 0 关注
  • 1249 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信