918.maximum-sum-circular-subarray.cpp

/*
 * [954] Maximum Sum Circular Subarray
 *
 * https://leetcode.com/problems/maximum-sum-circular-subarray/description/
 *
 * algorithms
 * Medium (26.06%)
 * Total Accepted:    3.9K
 * Total Submissions: 14.8K
 * Testcase Example:  '[1,-2,3,-2]'
 *
 * 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:
 *
 *
 * -30000 <= A[i] <= 30000
 * 1 <= A.length <= 30000
 *
 *
 *
 *
 *
 *
 */

class Solution {
 public:
  int kadane(vector<int>& A) {
    int maxSum = INT_MIN;
    int maxSoFar = 0;

    for (int i = 0; i < A.size(); ++i) {
      maxSoFar =
          max(A[i],
              maxSoFar + A[i]);  // maxSoFar is the max sum ending at this point
      maxSum =
          max(maxSum, maxSoFar);  // maxSum is the largest maxSoFar till now
    }
    return maxSum;
  }

  int maxSubarraySumCircular(vector<int>& A) {
    // Kadane's algorithm after reversing signs
    int totalSum = 0;
    bool allNegative = true;

    for (int& i : A) {
      totalSum += i;
      if (allNegative && i > 0) {
        allNegative = false;
      }
    }

    int maxNormal = kadane(A);

    if (allNegative) {
      // if all negative values than the circular arrays will only make it
      // smaller
      // so assume its not circular and find the maximum
      return maxNormal;
    } else {
      // if at least one is positive then run kadanes normally
      // and run with signs reversed
      // signs reversed kadane is the abs(minimum negative sum)
      for (int& i : A) {
        i = i * (-1);
      }
      int minimumNegativeSum = kadane(A);
      // add it to the total sum to get the remaining maximum positive sum
      int maxSignsReversed = totalSum + minimumNegativeSum;
      // take the max of the two --> WHY??
      // because total sum - minimum negative sum  != maximum positive sum
      // eg. [1, -2, 3, 1, -2], maxNormal = 4, abs(minimum negative sum) = 2,
      // total = 1, maxSignsReversed = 2 (3 + 1- 2 + 1) IT WRAPS WHEN SIGNS ARE
      // REVERSED!
      return max(maxNormal, maxSignsReversed);
    }
  }
};