Problem
You’re given an array of size N. You’ve to find the maximum sum obtained from a contiguous subarray of size k of the given array, where k <= N.
Example 1:
Input: arr[] = {10, 40, 30, 50}, k = 2
Output: 80
Explanation: Subarray arr[2,3] ie arr[2] + arr[3] gives the maximum sum (30+50 = 80)
Naive Approach
We could run two loops from i=0 to n-k and j=i to i+k-1, where n is the size of the array. And we keep updating the maximum sum value
Pseudocode
1. for i=0 to n-k: 2. currSum = 0; 3. for j=i to i+k-1: 4. currSum += arr[j]; 5. maxSum = max(maxSum, currSum) 6. return maxSum
Code Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | //// main.cpp// Subarray with max sum//// Created by Himanshu on 18/09/21.//#include <iostream>#include <climits>using namespace std;const int N = 7;int solve (int A[], int k) { int maxSum = INT_MIN; for (int i=0; i<=N-k; i++) { int currSum = 0; for (int j=i; j<=(i+k-1); j++) { currSum += A[j]; } maxSum = max(maxSum, currSum); } return maxSum;} int main() { int A[N] = {5, 3, 4, 6, 8, 11, 20}; int k = 7; cout<<"Maximum subset sum: "<<solve(A, k)<<endl; k = 4; cout<<"Maximum subset sum: "<<solve(A, k)<<endl; } |
Output:
Maximum subset sum: 57 Maximum subset sum: 45
Time complexity of the above solution is O(N*k)
Sliding window technique
The Sliding window is a problem-solving technique for problems that involve finding subarrays of an array with given sum or minimum/maximum sum. These problems could be solved by brute force approach in O(n2). Using the ‘sliding window’ technique, we can reduce the time complexity to O(n).
A sliding window is a contiguous sub-list that runs over an underlying collection i.e., if you have an array like
[5, 3, 4, 6, 8, 11, 20]
A sliding window of size 3 would be like
[5, 3, 4], 6, 8, 11, 20 5, [3, 4, 6], 8, 11, 20 5, 3, [4, 6, 8], 11, 20 5, 3, 4, [6, 8, 11], 20 5, 3, 4, 6, [8, 11, 20]
Find maximum sum of contiguous subarray solution
Pseudocode
SlidingWindow(A, k) 1. currSum = 0, maxSum = INT_MIN 2. for i=0 to k: 3. currSum += A[i] 4. maxSum = max(currSum, maxSum) 5. for i=k to n-1: 6. currSum += arr[i] - arr[i-k] 7. maxSum = max(maxSum, currSum) 8. return maxSum
Code Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | //// main.cpp// Sliding Window//// Created by Himanshu on 18/09/21.//#include <iostream>#include <climits>using namespace std;const int N = 7;int solve (int A[], int k) { int maxSum = INT_MIN, currSum = 0; for (int i=0; i<k; i++) { currSum += A[i]; } maxSum = max(maxSum, currSum); for (int i=k; i<N; i++) { currSum += A[i] - A[i-k]; maxSum = max(maxSum, currSum); } return maxSum;} int main() { int A[N] = {5, 3, 4, 6, 8, 11, 20}; int k = 7; cout<<"Maximum subset sum: "<<solve(A, k)<<endl; k = 4; cout<<"Maximum subset sum: "<<solve(A, k)<<endl; } |
Output:
Maximum subset sum: 57 Maximum subset sum: 45
Time complexity of the above solution is O(N)
Here’s a working example: Ideone