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

Example 4:

Input: [3,-2,2,-3] Output: 3 Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1] Output: -1 Explanation: Subarray [-1] has maximum sum -1

Note:

  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000

Solution

Here we can apply Kadane’s Algorithm to get the largest sum from continuous subarray, Kadane’s logic will work if array is not a circular array. Here given array is circular array so continuous sub array may have few elements from tail and few are from the head of the array.

There can be two cases for the maximum sum:

1. Subarray lies between the elements, in that case normal Kadane’s algorithm will work.

For example:

Input: [1,-2,3,4,-2] Output: 7 Explanation: Subarray [3,4] lies between the array.

2. Subarray contains wrapped elements, few elements from tail and few are from head.

For example:

Input: [5,3,-3,5,6] Output: 19 Explanation: Subarray [5,6,5,3] contributes to the maxsum. To get the result we need to remove middle portion.

In this case our main array can be splited into three parts head=[5,3] middle=[-3] tail=[5,6] Total_Sum_of_Array = head_sum + middle_sum + tail_sum Total_Sum_of_Array – middle_sum = head_sum + tail_sum

Through Total_Sum_of_Array – middle_sum = head_sum + tail_sum equation we can get the maxsum of wrapped array.

We can calculate Total_Sum_of_Array, only missing part is to find the middle portion and sum of that. To get that we can revert all the elements with opposite sign (+ -> – and – -> +) and apply Kadane’s algorithm on that array, which gives the sum of the middle elements.

Based on the above two approaches, return maximum out of it.

Code

Output

10

Complexity Analysis

Time complexity: O(N).
Space Complexity: O(1).

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *