科大讯飞笔试真题求解

11月10号的科大讯飞笔试题最后一题,考场上没做出来,考完还是没想出来,哪位大佬有思路?

题目大意:给出一个数组arr,数组元素均为非负整数,从数组中的某一个元素出发,假设初始元素索引为x,则初始区间为
[x, x],令count表示当前区间内所有元素的总和,初始时count为arr[x],向左或向右扩展区间,每次只能扩展1步,要求被纳入区间内的元素,其值必须大于当前count,求问给定任意一个数组中元素的索引,它对应的count最大能达到多少?

示例:数组[2, 1, 4],从元素1开始,第一步可以向右扩展为 [1, 4] ,此时count为5,左边的2小于5因此无法再扩展,或者第一步向左扩展为 [2,1],此时count为3,于是又可以向右扩展到4,此时count为7。因此count最大为7

我个人猜测可以用动态规划或者深度优先搜索解决,但深度搜索对于数组很大的情况下时间复杂度过高,动态规划又想不出递推条件,问chatgpt4给的也都是错误答案,有没有大佬能解答这个问题?

引流:#秋招##美团##腾讯# #科大讯飞##笔试#
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务