Maximum Subarray Sum With Length Divisible by K

• Initialize maxSum to a very small number (e.g., Long.MIN_VALUE) and a boolean flag found to false.
• Iterate through the array with an outer loop for the start index i from 0 to n-1.
• Inside the outer loop, initialize a currentSum to 0.
• Start an inner loop for the end index j from i to n-1.
• In the inner loop, add nums[j] to currentSum.
• Calculate the length of the current subarray: length = j - i + 1.
• If length % k == 0, it means we have found a valid subarray.
  • Set found to true.
  • Update maxSum by taking the maximum of the current maxSum and currentSum.
• After the loops complete, if found is true, return maxSum. Otherwise, return 0. (Note: The problem constraints 1 <= k <= nums.length guarantee that at least one valid subarray exists, so found will always be true. Returning maxSum directly after initializing it to Long.MIN_VALUE is sufficient).

We can implement this using two nested loops. The outer loop iterates through all possible starting indices i of a subarray, and the inner loop iterates through all possible ending indices j. For each pair of (i, j), we have a subarray nums[i...j]. We then check if its length, j - i + 1, is divisible by k. To avoid a third loop for calculating the sum, which would lead to an O(N³) complexity, we can maintain a running sum within the inner loop. We start with currentSum = 0 for each starting index i and accumulate the values as j increases. Whenever the length condition is met, we update our global maxSum. Since the sum of elements can be large, we should use a long data type for sums. We initialize maxSum to a very small value to correctly handle cases where all subarray sums are negative.

1class Solution {2    public long maximumSubarraySum(int[] nums, int k) {3        int n = nums.length;4        long maxSum = Long.MIN_VALUE;5        boolean found = false;6 7        for (int i = 0; i < n; i++) {8            long currentSum = 0;9            for (int j = i; j < n; j++) {10                currentSum += nums[j];11                int length = j - i + 1;12                if (length > 0 && length % k == 0) {13                    found = true;14                    maxSum = Math.max(maxSum, currentSum);15                }16            }17        }18 19        // According to constraints, a valid subarray always exists.20        // If it didn't, returning 0 might be a sensible default.21        return found ? maxSum : 0;22    }23}

• Let P[x] be the prefix sum nums[0] + ... + nums[x-1], with P[0] = 0.
• The sum of a subarray nums[i...j] is P[j+1] - P[i].
• The length of this subarray is (j+1) - i. We need this to be a multiple of k, which means ((j+1) - i) % k == 0, or (j+1) % k == i % k.
• The problem is now to find max(P[p] - P[q]) for indices p > q where p % k == q % k.
• To maximize P[p] - P[q] for a given p, we need to find the minimum P[q] for all q < p with the same remainder modulo k.
• We can achieve this in a single pass:
  1. Initialize maxSum = Long.MIN_VALUE.
  2. Initialize a map or an array minPrefixSum to store the minimum prefix sum seen for each remainder modulo k. Initialize values to a large number.
  3. Set minPrefixSum[0] = 0 to account for the initial empty prefix (P[0]=0).
  4. Initialize currentPrefixSum = 0.
  5. Iterate through nums from i = 0 to n-1: a. Update currentPrefixSum += nums[i]. This sum represents P[i+1]. b. Calculate the remainder r = (i + 1) % k. c. Check if minPrefixSum has an entry for r. If it does, it means we've seen a previous prefix sum P[q] where q % k == r. The difference currentPrefixSum - minPrefixSum[r] is a candidate for the maximum sum. d. Update maxSum = max(maxSum, currentPrefixSum - minPrefixSum[r]). e. Update minPrefixSum[r] with the minimum value between its current value and currentPrefixSum.
• Return maxSum (or 0 if no valid subarray is found, though constraints prevent this).

Let P[x] be the prefix sum of the first x elements of nums. The sum of a subarray from index i to j is P[j+1] - P[i]. The length of this subarray is j - i + 1. We are given that the length must be a multiple of k, so (j - i + 1) % k == 0. This simplifies to (j + 1) % k == i % k.

This transforms the problem into finding two prefix sum indices, say p = j + 1 and q = i, such that p % k == q % k and the difference P[p] - P[q] is maximized. To maximize this difference for a given p, we need to subtract the smallest possible P[q] that we have encountered so far among all q < p that satisfy the remainder condition.

We can solve this by iterating through the array once while calculating the prefix sum. We use a hash map or an array of size k to keep track of the minimum prefix sum encountered for each remainder r from 0 to k-1. For each new prefix sum P[p], we check our map for the minimum P[q] with the same remainder and update our maxSum if P[p] - P[q] is larger. Then, we update the map with the current P[p] if it's smaller than the existing minimum for its remainder.

1import java.util.Map;2import java.util.HashMap;3 4class Solution {5    public long maximumSubarraySum(int[] nums, int k) {6        int n = nums.length;7        Map<Integer, Long> minPrefixSumMap = new HashMap<>();8        // Base case: a prefix sum of 0 at index -1 (logically P[0])9        // The remainder of index 0 is 0 % k = 0.10        minPrefixSumMap.put(0, 0L);11 12        long currentPrefixSum = 0L;13        long maxSum = Long.MIN_VALUE;14 15        for (int i = 0; i < n; i++) {16            currentPrefixSum += nums[i];17            // The current prefix sum is P[i+1]. The index is i+1.18            int remainder = (i + 1) % k;19 20            if (minPrefixSumMap.containsKey(remainder)) {21                long prevMinSum = minPrefixSumMap.get(remainder);22                maxSum = Math.max(maxSum, currentPrefixSum - prevMinSum);23            }24 25            // Update the map with the minimum prefix sum for this remainder.26            minPrefixSumMap.put(remainder, Math.min(minPrefixSumMap.getOrDefault(remainder, Long.MAX_VALUE), currentPrefixSum));27        }28 29        // If maxSum was never updated, it means no valid subarray was found.30        // Per constraints, this won't happen. If it could, returning 0 would be a safe bet.31        return maxSum == Long.MIN_VALUE ? 0 : maxSum;32    }33}