急!跪求答案!Dev-C++贪心算法编程题
连续数之和最大值(maxsum) 题目大意: 给出一个长度为N的数列(数列中至少有一个正数),要求求出其中的连续数之和的最大值。(也可以加入a和b来限制连续数的长度不小于a且不大于b)。 解题思路: 先说不加限制的那种,定义一个统计变量tot,然后用循环进行如下操作:inc(tot,item) 其中如果出现tot<0的情况,则将tot赋值为0。在循环过程之中tot出现的最大值即为答案。 如果加入了限制条件的话,问题就变得难一些了。为此我们先定义数组sum[i]来表示code[1]到code[i]之和(这样的话code[a]~code[b]的和我们就可以用sum[b]-sum[a-1]来表示了。)。 再维护一个数组hash[i]来表示满足条件的sum[a-1]的下标,并使之按递增顺序排列,这样当前以第i的数为终止的数列的最大值肯定就是sum[i]-sum[hash[1]]。 现在我们来讨论hash数组之中的数据需要满足的条件和如何维护的具体问题: 当考虑到以第i个数为结尾时,hash[i]所表示的下标需要满足的第一个条件就是题目规定的长度限制,我们需要实时的加入满足长度规定的下标,删除不符合要求的下标。其次,与不加限制条件时相同,若sum[i]-sum[hash[1]]的值小于零,则清空数组hash。 维护时可以这样,当考虑到第i个数时,我们就将下标i-a+1加入到hash中,因为hash中原来已经排好序,因此我们我们可以用插入排序来维护hash的递增性,然后我们考察hash[1],若hash[1]<i-b+1,则证明其已超出长度限制,我们就将其删除,接着再考虑更新后的hash[1],如此重复直至找到一个满足条件的hash[1]为止。 我们可以用链表来表示hash,这样就可以减少数据加入和删除时频繁数据移动的时间消耗。 记录下sum[i]-sum[hash[1]]的最大值即为答案。 各位Dev-C++编程高手,帮一下我吧。今天下午5点前要交货了。谢谢
去百度一下吧`兄弟
答:这种算法称为为贪心算法,也叫贪婪算法或启发式算法,它对整个求解过程的局部做最优调整,它只适用于求较优解或者部分解,而不能求最优解详情>>
答:详情>>
答:网络教育是要参加入学考试的,是高校组织的入学考试,考试很简单,别担心,你把它给你的题都记住,考试基本就可以过关。详情>>