Lintcode402 Continuous Subarray Sum solution 题解
发布在刷题能手——Lintcode 题解2018年4月13日view:259
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

给定一个整数数组,请找出一个连续子数组,使得该子数组的和最大。输出答案时,请分别返回第一个数字和最后一个数字的下标。(如果两个相同的答案,请返回其中任意一个)

【题目链接】

www.lintcode.com/en/problem/continuous-subarray-sum/

【题目解析】

此题与题目Maximum Subarray几乎一模一样,只是返回值要求不一样。

由于需要返回区间索引值,那么显然需要额外变量记录区间起止处。若使用题解2中提到的sum - minSum的区间和更新方式,索引终止处容易得知是sum - minSum > maxSub时的i, 问题是索引起始处如何确定。容易得知索引起始处如果更新,必然在minSum > sum时,但问题在于满足此条件的可能不止一处,所以我们需要先记录这个索引值并在sum - minSum > maxSub时判定索引终止值是否大于索引起始值,不小于则更新。注意更新索引值。

【参考答案】

www.jiuzhang.com/solutions/continuous-subarray-sum/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏