2.1.6. Questions

2.1.6.1. Maximum Subarray

Given an integer array nums, find the subarray which has the largest sum and return its sum.

int maxSubArray(vector<int> nums) {
    int g=INT_MIN, l=0;
    for(int i: nums) l=max(l,0)+i, g=max(g,l);
    return g;
}

πŸ‘½ Also find the indices of the max subarray range

There is another way to use cumulative sum to get the max subarray.

tuple<int, int, int> maxSubArray_followup3(vector<int> nums) {
    int cs=nums[0], r=cs, i=0, j=0;
    int mi=min(0,cs);  // πŸ’£ [1,2,3]
    for(int k=1; k<nums.size(); k++){
        cs += nums[k];
        if (r<cs-mi) j=k, r=cs-mi;
        if (mi>cs) i=k+1, mi=cs;
    }
    if(i>j) i=j;  // πŸ’£ [-10,-2,-3,-4]
    return {i,j,r};
}

2.1.6.2. Maximum Score Of Spliced Array

Imagine you have two lists of numbers, called nums1 and nums2, each with the same number of elements. You can choose to swap any continuous section (from one element up to the whole list) of these two lists with each other. After swapping, the score is determined by which list has the highest total sum of numbers.

Your task is to figure out if you should swap any part of these lists to make the score (the highest total of either list) as big as possible. Sometimes, it might be best not to swap anything at all.

Here are a few examples to help you understand:

  • Example 1:

    Lists: nums1 = [60, 60, 60], nums2 = [10, 90, 10]

    If you swap the second element of each list, nums1 becomes [60, 90, 60] and nums2 becomes [10, 60, 10]. The score now would be the highest total from either list, which is 210 from nums1.

  • Example 2:

    Lists: nums1 = [20, 40, 20, 70, 30], nums2 = [50, 20, 50, 40, 20]

    If you swap the last two elements, nums1 changes to [20, 40, 20, 40, 20] and nums2 changes to [50, 20, 50, 70, 30]. The highest total here is 220 from nums2.

  • Example 3:

    Lists: nums1 = [7, 11, 13], nums2 = [1, 1, 1]

    In this case, it’s better not to swap anything because nums1 already adds up to more than nums2. The score would be 31 from nums1. Your goal is to determine the highest possible score you can achieve by either swapping or not swapping parts of these lists.

Code Block 2.1.8 Max Sum After Swap
 1    int maxScoreAfterSwap(vector<int> &nums1, vector<int> &nums2) {
 2        int g = INT_MIN, l = 0, cs = 0;
 3        for (int i = 0; i < nums1.size(); i++) {
 4            cs += nums1[i];
 5            l = max(l, 0) + nums2[i] - nums1[i], g = max(g, l);
 6        }
 7        if (g > 0) cs += g;
 8        int g2 = INT_MIN, l2 = 0, cs2 = 0;
 9        for (int i = 0; i < nums2.size(); i++) {
10            cs2 += nums2[i];
11            l2 = max(l2, 0) + nums1[i] - nums2[i], g2 = max(g2, l2);
12        }
13        if (g2 > 0) cs2 += g2;
14        return max(cs, cs2);
15    }