Itint5-面试题总结 - Backyard of LixinZhang

Itint5-面试题总结 - Backyard of LixinZhang

环形数组的子数组最大和

题目

有一个包含n个元素的首尾相连的环形数组arr，计算最大的子段和（允许空段）。

样例：数组[1, 3, -2, 6, -1]，最大子段和应该为9，对应的子段为[6, -1, 1, 3]。

分析

两种情况，一种包括中间分割点，另一种不包括。

不包括是经典的求最大连续子数组和的题目，得到$max_sub_arr$。 包括的话，是求（总和$sum$ - 最小连续子数组和$min_sub_arr$）。

最终结果为 max(maxsubarr,sum−minsubarr)

Read full article from Itint5-面试题总结 - Backyard of LixinZhang