Skip to content

2321. Maximum Score Of Spliced Array 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
    return max(kadane(nums1, nums2), kadane(nums2, nums1));
  }

 private:
  // How much nums1 can gain by swapping a part of the array
  int kadane(const vector<int>& nums1, const vector<int>& nums2) {
    int gain = 0;
    int maxGain = 0;

    for (int i = 0; i < nums1.size(); ++i) {
      gain = max(0, gain + nums2[i] - nums1[i]);
      maxGain = max(maxGain, gain);
    }

    return maxGain + accumulate(nums1.begin(), nums1.end(), 0);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int maximumsSplicedArray(int[] nums1, int[] nums2) {
    return Math.max(kadane(nums1, nums2), kadane(nums2, nums1));
  }

  // How much nums1 can gain by swapping a part of the array
  private int kadane(int[] nums1, int[] nums2) {
    int gain = 0;
    int maxGain = 0;

    for (int i = 0; i < nums1.length; ++i) {
      gain = Math.max(0, gain + nums2[i] - nums1[i]);
      maxGain = Math.max(maxGain, gain);
    }

    return maxGain + Arrays.stream(nums1).sum();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
      # How much nums1 can gain by swapping a part of the array
    def kadane(nums1: List[int], nums2: List[int]) -> int:
      gain = 0
      maxGain = 0

      for n1, n2 in zip(nums1, nums2):
        gain = max(0, gain + n2 - n1)
        maxGain = max(maxGain, gain)

      return maxGain + sum(nums1)

    return max(kadane(nums1, nums2), kadane(nums2, nums1))