3196. Maximize Total Cost of Alternating Subarrays

Approach 1: Indexed-based for loop

• Time: $O(n)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  long long maximumTotalCost(vector<int>& nums) {
    long keep = nums[0];  // the maximum cost if the last number is kept
    long flip = nums[0];  // the maximum cost if the last number is flipped

    for (int i = 1; i < nums.size(); ++i) {
      const long keepCurr = max(keep, flip) + nums[i];
      const long flipCurr = keep - nums[i];
      keep = keepCurr;
      flip = flipCurr;
    }

    return max(keep, flip);
  }
};

class Solution {
  public long maximumTotalCost(int[] nums) {
    long keep = nums[0]; // the maximum cost if the last number is kept
    long flip = nums[0]; // the maximum cost if the last number is flipped

    for (int i = 1; i < nums.length; ++i) {
      final long keepCurr = Math.max(keep, flip) + nums[i];
      final long flipCurr = keep - nums[i];
      keep = keepCurr;
      flip = flipCurr;
    }

    return Math.max(keep, flip);
  }
}

class Solution:
  def maximumTotalCost(self, nums: list[int]) -> int:
    keep = nums[0]  # the maximum cost if the last number is kept
    flip = nums[0]  # the maximum cost if the last number is flipped

    for i in range(1, len(nums)):
      keepCurr = max(keep, flip) + nums[i]
      flipCurr = keep - nums[i]
      keep = keepCurr
      flip = flipCurr

    return max(keep, flip)

Approach 2: Range-based for loop

• Time: $O(n)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  long long maximumTotalCost(vector<int>& nums) {
    // A small trick so that we don't need to handle the edge case and can use
    // ranged-based for loop.
    long keep = LONG_MIN / 2;  // the maximum cost if the last number is kept
    long flip = 0;             // the maximum cost if the last number is flipped

    for (const int num : nums) {
      const long keepCurr = max(keep, flip) + num;
      const long flipCurr = keep - num;
      keep = keepCurr;
      flip = flipCurr;
    }

    return max(keep, flip);
  }
};

class Solution {
  public long maximumTotalCost(int[] nums) {
    // A small trick so that we don't need to handle the edge case and can use
    // ranged-based for loop.
    long keep = Long.MIN_VALUE / 2; // the maximum cost if the last number is kept
    long flip = 0;                  // the maximum cost if the last number is flipped

    for (final int num : nums) {
      final long keepCurr = Math.max(keep, flip) + num;
      final long flipCurr = keep - num;
      keep = keepCurr;
      flip = flipCurr;
    }

    return Math.max(keep, flip);
  }
}

class Solution:
  def maximumTotalCost(self, nums: list[int]) -> int:
    # A small trick so that we don't need to handle the edge case and can use
    # ranged-based for loop.
    keep = -math.inf  # the maximum cost if the last number is kept
    flip = 0  # the maximum cost if the last number is flipped

    for num in nums:
      keep, flip = max(keep, flip) + num, keep - num

    return max(keep, flip)