Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2321.html

2321. Maximum Score Of Spliced Array

  • Difficulty: Hard.
  • Related Topics: Array, Dynamic Programming.
  • Similar Questions: Maximum Subarray.

Problem

You are given two 0-indexed integer arrays nums1 and nums2, both of length n.

You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].

  • For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2, nums1 becomes [1,**12,13**,4,5] and nums2 becomes [11,**2,3**,14,15].

You may choose to apply the mentioned operation once or not do anything.

The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.

Return the **maximum possible score**.

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

  Example 1:

Input: nums1 = [60,60,60], nums2 = [10,90,10]
Output: 210
Explanation: Choosing left = 1 and right = 1, we have nums1 = [60,90,60] and nums2 = [10,60,10].
The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.

Example 2:

Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
Output: 220
Explanation: Choosing left = 3, right = 4, we have nums1 = [20,40,20,40,20] and nums2 = [50,20,50,70,30].
The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.

Example 3:

Input: nums1 = [7,11,13], nums2 = [1,1,1]
Output: 31
Explanation: We choose not to swap any subarray.
The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.

  Constraints:

  • n == nums1.length == nums2.length

  • 1 <= n <= 105

  • 1 <= nums1[i], nums2[i] <= 104

Solution

  • class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int sum1 = 0;
        int sum2 = 0;
        int n = nums1.length;
        for (int num : nums1) {
            sum1 += num;
        }
        for (int num : nums2) {
            sum2 += num;
        }
        if (sum2 > sum1) {
            int temp = sum2;
            sum2 = sum1;
            sum1 = temp;
            int[] temparr = nums2;
            nums2 = nums1;
            nums1 = temparr;
        }
        // now sum1>=sum2
        // maxEndingHere denotes the maximum sum subarray ending at current index(ie. element at
        // current index has to be included)
        // minEndingHere denotes the minimum sum subarray ending at current index
        int maxEndingHere;
        int minEndingHere;
        int maxSoFar;
        int minSoFar;
        int currEle;
        maxEndingHere = minEndingHere = maxSoFar = minSoFar = nums2[0] - nums1[0];
        for (int i = 1; i < n; i++) {
            currEle = nums2[i] - nums1[i];
            minEndingHere += currEle;
            maxEndingHere += currEle;
            if (maxEndingHere < currEle) {
                maxEndingHere = currEle;
            }
            if (minEndingHere > currEle) {
                minEndingHere = currEle;
            }
            maxSoFar = Math.max(maxEndingHere, maxSoFar);
            minSoFar = Math.min(minEndingHere, minSoFar);
        }
        // return the maximum of the 2 possibilities dicussed
        // also keep care that maxSoFar>=0 and maxSoFar<=0
        return Math.max(sum1 + Math.max(maxSoFar, 0), sum2 - Math.min(0, minSoFar));
    }
}

############

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int s1 = 0, s2 = 0, n = nums1.length;
        for (int i = 0; i < n; ++i) {
            s1 += nums1[i];
            s2 += nums2[i];
        }
        return Math.max(s2 + f(nums1, nums2), s1 + f(nums2, nums1));
    }

    private int f(int[] nums1, int[] nums2) {
        int t = nums1[0] - nums2[0];
        int mx = t;
        for (int i = 1; i < nums1.length; ++i) {
            int v = nums1[i] - nums2[i];
            if (t > 0) {
                t += v;
            } else {
                t = v;
            }
            mx = Math.max(mx, t);
        }
        return mx;
    }
}

  • class Solution:
    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
        def f(nums1, nums2):
            d = [a - b for a, b in zip(nums1, nums2)]
            t = mx = d[0]
            for v in d[1:]:
                if t > 0:
                    t += v
                else:
                    t = v
                mx = max(mx, t)
            return mx

        s1, s2 = sum(nums1), sum(nums2)
        return max(s2 + f(nums1, nums2), s1 + f(nums2, nums1))

############

# 2321. Maximum Score Of Spliced Array
# https://leetcode.com/problems/maximum-score-of-spliced-array/

class Solution:
    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        
        def kadane(nums):
            curr = res = 0
            
            for x in nums:
                curr = max(x, curr + x)
                res = max(res, curr)
            
            return res
        
        def g(A, B):
            return sum(A) + kadane([b - a for a, b in zip(A, B)])
        
        return max(g(nums1, nums2), g(nums2, nums1))


  • class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int s1 = 0, s2 = 0, n = nums1.size();
        for (int i = 0; i < n; ++i) {
            s1 += nums1[i];
            s2 += nums2[i];
        }
        return max(s2 + f(nums1, nums2), s1 + f(nums2, nums1));
    }

    int f(vector<int>& nums1, vector<int>& nums2) {
        int t = nums1[0] - nums2[0];
        int mx = t;
        for (int i = 1; i < nums1.size(); ++i) {
            int v = nums1[i] - nums2[i];
            if (t > 0)
                t += v;
            else
                t = v;
            mx = max(mx, t);
        }
        return mx;
    }
};

  • func maximumsSplicedArray(nums1 []int, nums2 []int) int {
	s1, s2 := 0, 0
	n := len(nums1)
	for i, v := range nums1 {
		s1 += v
		s2 += nums2[i]
	}
	f := func(nums1, nums2 []int) int {
		t := nums1[0] - nums2[0]
		mx := t
		for i := 1; i < n; i++ {
			v := nums1[i] - nums2[i]
			if t > 0 {
				t += v
			} else {
				t = v
			}
			mx = max(mx, t)
		}
		return mx
	}
	return max(s2+f(nums1, nums2), s1+f(nums2, nums1))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions