思路：由于數(shù)組元素總和是固定值，因而跨頭、尾的連續(xù)子數(shù)組和最大，等價(jià)于求 中間那段和最小。因此，問(wèn)題轉(zhuǎn)為計(jì)算 連續(xù)子數(shù)組的最大和 與 連續(xù)子數(shù)組的最小和
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()
{
}