Apple OA 面试真题解析：Maximum Sum of a Circular Subarray｜数组与动态规划

Given an integer array, find the maximum sum of a contiguous subarray.

Update the solution when the array is circular, meaning the last element connects to the first element.

这道题要求在普通数组和环形数组两种情况下都求连续子数组的最大和。经典做法是先用 Kadane 算法求普通最大子数组和；如果数组是环形的，答案要么是这个普通最大值，要么是“总和减去最小子数组和”，表示选取跨越首尾的那一段。需要注意的是，如果所有元素都是负数，不能用总和减最小值的结果，否则会把空子数组算进去，因此要单独处理。