Maximum K-Subarray Sum Editorial

Practice Problem Link: Maximum K-Subarray Sum

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array and a number k, find the sum of the subarray that has the maximum sum among all the subarrays of size k.

Naive Approach

The naive approach is to iterate over all the subarrays in the array, and if it is of length k, we can calculate its sum and take the maximum out of it.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(1)

Implementation

C++

int maxKSubarraySum(vector<int> A, int k) {
	int n = A.size();
	int maximum = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			if(j - i + 1 == k) {
				int sum = 0;
				for(int l = i; l <= j; l++) {
					sum += A[l];
				}
				maximum = max(maximum, sum);
			}
		}
	}
	return maximum;
}

Java

class Solution {
	int maxKSubarraySum (int[] A, int k) {
		int n = A.length;
		int maximum = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(j - i + 1 == k) {
					int sum = 0;
					for(int l = i; l <= j; l++) {
						sum += A[l];
					}
					maximum = Math.max(maximum, sum);
				}
			}
		}
		return maximum;
	}
}

Optimal Approach

In the optimal approach, we will use the sliding window technique to calculate the sum in linear time. We keep erasing the i - kth element from the current sum and add the ith element to the sum, and again take the maximum from the current sum and the previous one. Finally, return the maximum result.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int maxKSubarraySum(vector<int> A, int k) {
	int n = A.size();
	int maximum = 0;
	int sum = 0;
	for(int i = 0; i < k; i++) {
		sum += A[i];
	}
	maximum = max(sum, maximum);
	for(int i = k; i < n; i++) {
		sum -= A[i - k];
		sum += A[i];
		maximum = max(sum, maximum);
	}
	return maximum;
}

Java

class Solution {
	int maxKSubarraySum (int[] A, int k) {
		int n = A.length;
		int maximum = 0;
		int sum = 0;
		for(int i = 0; i < k; i++) {
			sum += A[i];
		}
		maximum = Math.max(sum, maximum);
		for(int i = k; i < n; i++) {
			sum -= A[i - k];
			sum += A[i];
			maximum = Math.max(sum, maximum);
		}
		return maximum;
	}
}