LeetCode： Maximum Sum Circular Subarray

Question

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]

Output: 3

Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]

Output: 10

Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]

Output: 4

Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Solution

此題目可以說是 Maximum Subarray 所衍生出來的另一個考題。 比較好的解法還是會運用到 Dynamic Programming 的技巧來做，但多了一點有趣的變化。 基本的解題概念是從陣列當中找出『最大負值的子結構』，然後從『原始的陣列結構』移除『最大負值的子結構』，留下來的就會是『最大正值的子結構』。

Example

陣列的結構：[5,-3,5]

最大負值的子結構：[-3]

最大正值的子結構： [5,-3,5] - [-3] = [5, 5]

除此之外，當你計算出『最大正值的子結構』還需要跟『非循環最大正值的子結構』比較，看哪個子結構的總和比較高，就是『最佳循環子結構的總和』。

Example

陣列的結構：[1,-2,3,-2]

最大負值的子結構：[-2]

最大正值的子結構： [1,-2,3,-2] - [-2] = [1,-2,3]

非循環最大正值的子結構： [3]

最佳循環子結構的總和: (1 + (-2) + 3) VS (3) => 3

另外需要特別注意的邊界案例(boundary case)，是當陣列內的元素都是負值的情況下，『最佳循環子結構的總和』就是陣列中負值最小的那ㄧ個。

如何能得知陣列內的元素都是負值呢？ 除了逐個的檢查外，可以比較『陣列結構的總和』與『最大負值的子結構的總和』是否相同，因為把陣列全部的負值元素加起來，就意味著得到『最大負值的子結構』。

Example

陣列的結構：[-2,-3,-1]

最大負值的子結構：[-2,-3,-1]

非循環最大正值的子結構： [-1]

最佳循環子結構的總和: [-1]

def max_subarray_sum_circular(nums)
  # 原始陣列中最大的元素
  orginal_max_num = nums.max

  # 原始陣列元素總和
  all_sum = nums.sum

  # 使用 Kadane’s Algorithm 取得在不循環下最大值子結構的總和
  max_sub_sum = kadane(nums)

  # 反轉原始陣列中的每一個元素的正負值，再使用 Kadane’s Algorithm 取得最大負值的子結構的總和
  nums = nums.map{|num| num * -1}
  min_sub_sum = -kadane(nums)

  # 檢查陣列中元素是否都是負值 (boundary case)，就要取負值最少的那ㄧ個
  return [orginal_max_num, max_sub_sum].max if all_sum == min_sub_sum

  # 比較『最大正值的子結構』VS『非循環最大正值的子結構』的總和，取得『最佳循環子結構的總和』
  original_max_sub_sum = [(all_sum - min_sub_sum), max_sub_sum].max
end

# Kadane’s Algorithm
def kadane(nums)
  max_here = 0
  max_so_far = nums[0]
  (0..nums.size-1).each do |i|
    max_here = max_here + nums[i].to_i
    if max_here < nums[i].to_i
      max_here = nums[i].to_i
    end
    if max_here > max_so_far
      max_so_far = max_here
    end
  end
  max_so_far
end