Problem Statement
Given an array of integers, the task is to find a contiguous subarray with the maximum sum. The subarray must consist of at least one element.
Examples
Example 1:
Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The maximum subarray sum for this array is the sum elements from index 3 to 6:
[4, -1, 2, 1] = 6Example 2:
Input: arr = [2, 3, 5, -2, 7, -4]
Output: 15
Explanation: The subarray from the index 0 to index 4 has the largest sum = 15Example 3:
Input: arr = [-2, -3, -7, -2, -10, -4]
Output: -2
Explanation: The element on index 0 or index 3 makes up the largest sum when taken as a subarray.Terms
Subarray -
- A subarray is a contiguous part of an array.
- It is formed by selecting a range of elements from the original array without changing the order of the remaining elements.
- For example, in the array
[1, 2, 3, 4],[2, 3]is a subarray.
Subsequence:
- A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.
- Unlike subarrays, elements in a subsequence are not required to be contiguous.
- For example, in the array
[1, 2, 3, 4],[1, 3]is a subsequence.
Different Approaches
1️⃣ Brute Force Approach
- Iterate through all possible subarrays and calculate the sum for each.
- Keep track of the maximum sum encountered.
- Time Complexity:
O(n^3)
Intuition:
The idea is to find out all the subarrays of the given array and while finding out the subarray calculate the sum of all the elements of that particular subarray. Finally, find out the maximum sum among them and that will be the result.
Approach:
- Iterate in the array lets say i, this variable will select every possible starting index of the subarray. The possible starting indices can vary from index 0 to index n-1(n = size of the array).
- Inside the loop, run another loop(say j) that will signify the ending index of the subarray. For every subarray starting from the index i, the possible ending index can vary from index i to n-1(n = size of the array).
- After that for each subarray starting from index i and ending at index j, iterate again to calculate the sum of all the elements(of that particular subarray). Use a max variable to store the maximum sum so far and finally, return the max variable.
Code:
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
//Function to find maximum sum of subarrays
int maxSubArray(vector<int>& nums) {
/* Initialize maximum sum with
the smallest possible integer*/
int maxi = INT_MIN;
// Iterate over each starting index of subarrays
for (int i = 0; i < nums.size(); i++) {
/* Iterate over each ending index
of subarrays starting from i*/
for (int j = i; j < nums.size(); j++) {
// Variable to store the sum of the current subarray
int sum = 0;
// Calculate the sum of subarray nums[i...j]
for (int k = i; k <= j; k++) {
sum += nums[k];
}
/* Update maxi with the maximum of its current
value and the sum of the current subarray*/
maxi = max(maxi, sum);
}
}
// Return the maximum subarray sum found
return maxi;
}
};
int main() {
vector<int> arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
//create an instance of Solution class
Solution sol;
int maxSum = sol.maxSubArray(arr);
//Print the max subarray sum
cout << "The maximum subarray sum is: " << maxSum << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N^3), whereNis the size of the array. Using three nested loops, each running approximatelyNtimes.
2️⃣ Better Approach
Intuition:
The better approach is to avoid triple looping structure mentioned previously that calculates the sum of each subarray. On observation we understand that to get the sum of the current subarray we just need to add the current element to the sum of the previous subarray, hence there is no need of third loop to do that.
Approach:
- Iterate in the array lets say i to select every possible starting index of the subarray. The possible starting indices can vary from index 0 to index n-1(n is the array size).
- Inside the loop, iterate again lets say j that will signify the ending index as well as the current element of the subarray. For every subarray starting from index i, the possible ending index can vary from index i to n-1(n is size of the array).
- Inside loop j, keep adding the current element to the sum of the previous subarray. Among all the sums, the maximum one will be the answer and return it.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find maximum sum of subarrays
int maxSubArray(vector<int>& nums) {
/* Initialize maximum sum with
the smallest possible integer*/
int maxi = INT_MIN;
// Iterate over each starting index of subarrays
for (int i = 0; i < nums.size(); i++) {
/* Variable to store the sum
of the current subarray*/
int sum = 0;
/* Iterate over each ending index
of subarrays starting from i*/
for (int j = i; j < nums.size(); j++) {
/* Add the current element nums[j] to
the sum i.e. sum of nums[i...j-1]*/
sum += nums[j];
/* Update maxi with the maximum of its current
value and the sum of the current subarray*/
maxi = max(maxi, sum);
}
}
// Return the maximum subarray sum found
return maxi;
}
};
int main() {
vector<int> arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
// Create an instance of Solution class
Solution sol;
int maxSum = sol.maxSubArray(arr);
// Print the max subarray sum
cout << "The maximum subarray sum is: " << maxSum << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N^2), for using two nested loops, each running approximatelyNtimes, hereNis the size of the array. - Space Complexity:
O(1)for not using any extra space.
3️⃣ Optimal Approach (Kadane's Algorithm)
Intuition:
The intuition of the algorithm is to not consider the subarray as a part of the answer if its sum is less than 0. A subarray with a sum less than 0 will always reduce the answer and so this type of subarray cannot be a part of the subarray with maximum sum.
Approach:
- Iterate in the array using a variable i & while iterating add the elements to the sum variable and consider the maximum one.
- If at any point the sum becomes negative, reset the sum to 0 as that will be not considered as a part of our answer. Finally, return the maximum sum.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find maximum sum of subarrays
int maxSubArray(vector<int>& nums) {
// maximum sum
long long maxi = LLONG_MIN;
// current sum of subarray
long long sum = 0;
// Iterate through the array
for (int i = 0; i < nums.size(); i++) {
// Add current element to the sum
sum += nums[i];
// Update maxi if current sum is greater
if (sum > maxi) {
maxi = sum;
}
// Reset sum to 0 if it becomes negative
if (sum < 0) {
sum = 0;
}
}
// Return the maximum subarray sum found
return maxi;
}
};
int main() {
vector<int> arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
// Create an instance of Solution class
Solution sol;
int maxSum = sol.maxSubArray(arr);
// Print the max subarray sum
cout << "The maximum subarray sum is: " << maxSum << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N)for single traversal, hereNis the size of the array. - Space Complexity:
O(1), for not using any extra space.