Leetcode Study Day 53

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

My solution

My solution is to initialise two variables, one is the currentMax, the other is the globalMax. currentMax is the maximum sum of the subarray that ends at the current index. globalMax is the maximum sum of the subarray that ends at any index. Then I iterate through the array and update the currentMax and globalMax at each index. Finally, I return the globalMax.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];
        for (int i = 1; i < nums.size(); i++){
            int currentElement = nums[i];
            currentMax = max(currentMax + currentElement, currentElement);
            globalMax = max (currentMax, globalMax);
        }
        return globalMax;
    }
};

Maximum Sum Circular Subarray

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], …, nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example 1:
Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:
Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:
Input: nums = [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Solution

In this code, we use Kadane’s algorithm to find the maximum subarray sum. Then we find the minimum subarray sum using Kadane’s algorithm on the uninverted array. The maximum wrap sum is the total sum minus the minimum subarray sum. Finally, we return the maximum of the globalMax and maxWrap.

Total Sum: This is the sum of all elements in the array.

Minimum Subarray Sum: This is the smallest possible sum of a contiguous subarray within the array. By finding the minimum subarray sum, you are effectively finding the part of the array that would “cost” you the least if you were to exclude it from the total sum.

Maximum Wrapping Subarray Sum: The maximum sum of a wrapping subarray is essentially the total sum of the array minus some contiguous segment that you exclude. Now, if you want to maximize the sum of the remaining subarray (which wraps around), you should exclude the segment that has the minimum sum. This is because excluding a segment with a larger sum would leave you with a smaller sum for the wrapping subarray.

Therefore, the maximum wrapping subarray sum can be calculated by subtracting the minimum subarray sum from the total sum of the array. This approach works as long as there is at least one element that is not part of the minimum sum subarray. This is why you need to check if the maximum subarray sum found by Kadane’s algorithm is negative: if it is, the entire array consists of negative elements, and thus, you cannot apply this wrapping logic.

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];
        int totalSum = nums[0];
        
        // Start from the first element for max subarray sum
        for (int i = 1; i < nums.size(); i++) {
            currentMax = max(nums[i], currentMax + nums[i]);
            globalMax = max(globalMax, currentMax);
            totalSum += nums[i]; // sum up all elements
        }
        
        // If all numbers are negative, return globalMax
        if(globalMax < 0) {
            return globalMax;
        }
        
        // Now find the minimum subarray sum using Kadane's algorithm on the uninverted array
        int currentMin = nums[0];
        int globalMin = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            currentMin = min(nums[i], currentMin + nums[i]);
            globalMin = min(globalMin, currentMin);
        }

        // The maximum wrap sum is the total sum minus the minimum subarray sum
        int maxWrap = totalSum - globalMin;

        return max(globalMax, maxWrap);
    }
};