思路:由于数组元素总和是固定值,因而跨头、尾的连续子数组和最大,等价于求 中间那段和最小。因此,问题转为计算 连续子数组的最大和 与 连续子数组的最小和
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()
{
}