雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

 

思路:由于数组元素总和是固定值,因而跨头、尾的连续子数组和最大,等价于求 中间那段和最小。因此,问题转为计算 连续子数组的最大和 与 连续子数组的最小和


import std.algorithm;

 

int ring_max_continue_sum(in int[] src)

{

 int min_sum = src[0], cur_min_sum = min_sum;

 int max_sum = src[0], cur_max_sum = max_sum;

 int total_sum = src[0];

 

 foreach (value; src[1 .. $]) {

    cur_min_sum = min(value, cur_min_sum + value);

    min_sum = min(min_sum, cur_min_sum);

  

    cur_max_sum = max(value, cur_max_sum + value);

    max_sum = max(max_sum, cur_max_sum);

  

    total_sum += value;

 }

 return max(max_sum, total_sum - min_sum);

}

 

unittest {

 auto ta = [3, -2, 3];

 auto tb = [3, 4, -2, 3, -7, 1, -3, 8];

 assert(ta.ring_max_continue_sum == 6);

 assert(tb.ring_max_continue_sum == 16);

}

 

void main()

{

}

 

posted on 2011-07-20 23:49 flyinghearts 阅读(2411) 评论(2)  编辑 收藏 引用 所属分类: 算法编程之美

评论

# re: 对环状数组求连续子数组的最大和[未登录] 2012-05-20 00:57 galaxy
如果数全为负,这种边界情况有问题。  回复  更多评论
  

# re: 对环状数组求连续子数组的最大和 2012-05-20 19:28 flyinghearts
@galaxy
确实是。

解决方法也很简单:

return max(max_sum, total_sum - min_sum);

改为:

if (max_sum < 0) return max_sum;
return max(max_sum, total_sum - min_sum);

或者改为:

if (total_sum == min_sum) return max_sum;
return max(max_sum, total_sum - min_sum);

  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理