Introduction:
In this article, we will discuss the Maximum Contiguous Subarray Sum algorithm also known as kadane's algorithm I. Given an array of integers, our goal is to find the maximum possible sum of contiguous elements ending at each position in the array. We will also return the overall maximum sum that can be achieved. We will explain the approach and provide a step-by-step algorithm to solve this problem efficiently. Let's dive in!
Problem Statement:
Given an array of integers, we need to find the maximum sum of contiguous elements ending at each position in the array. Additionally, we need to return the overall maximum sum that can be achieved.
Approach:
To solve this problem, we can use dynamic programming. We'll create a dp[] vector of the same size as the input array to store the maximum sum of contiguous elements ending at each position. We'll initialize dp[0] with the first element of the array. Then, we'll iterate through the array from the second element onwards and update dp[i] using the formula: dp[i] = max(arr[i], arr[i] + dp[i-1]). This formula ensures that we consider the current element as the starting point of a new subarray or add it to the existing subarray ending at the previous position. Finally, we'll return the maximum value in the dp[] vector as the overall maximum sum.
Algorithm:
- Initialize a dp[] vector of the same size as the input array.
- Set dp[0] as the first element of the array.
- Initialize a variable res as dp[0].
- Iterate through the array from the second element:
- Update dp[i] as max(arr[i], arr[i] + dp[i-1]).
- Update res as max(res, dp[i]).
- Print dp[i-1].
- Print dp[sizeOfArray-1].
- Return res as the overall maximum sum.
Let's understand the algorithm with the help of examples:
Example 1:
Input:
N = 6
arr[] = {5, -2, -3, 32, -5, 65}
dp[]: 5 -2 -3 32 27 92
The maximum sum at each index is 5, -2, -3, 32, 27, 92. The maximum sum for a contiguous subarray is 92.
Example 2:
Input:
N = 5
arr[] = {-9, -8, 8, 3, -4}
dp[]: -9 -8 8 11 7
The maximum sum at each index is -9, -8, 8, 11, 7. The maximum sum for a contiguous subarray is 11.
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to calculate the maximum contiguous subarray sum ending at each position in the array
// and return the overall maximum.
long long maximumSum(int arr[], int sizeOfArray) {
// Creating a vector to store the maximum sum at each index
vector<long long> dp(sizeOfArray, 0);
// Initializing the first element of dp as the first element of arr
dp[0] = arr[0];
// Initializing the result as the first element of dp vector
long long res = dp[0];
// Main processing loop
for (int i = 1; i < sizeOfArray; i++) {
// Calculating the maximum sum at the current index
dp[i] = max((long long)arr[i], arr[i] + dp[i - 1]);
// Updating the overall maximum sum
res = max(res, dp[i]);
}
return res; // Returning the overall maximum sum
}
};
int main() {
int sizeOfArray;
cin >> sizeOfArray;
int arr[sizeOfArray];
// Taking input for the array elements
for (int i = 0; i < sizeOfArray; i++)
cin >> arr[i];
Solution ob;
cout << ob.maximumSum(arr, sizeOfArray) << endl;
return 0;
}
Conclusion:
In this article, we explored the Maximum Contiguous Subarray Sum algorithm. By using dynamic programming, we efficiently calculated the maximum sum of contiguous elements ending at each position in the array. We discussed the approach, provided a step-by-step algorithm, and illustrated it with examples. This algorithm allows us to find the maximum subarray sum and can be applied to similar problems involving contiguous subarray calculations.
