Kadane algorithm introduction
Kadane algorithm was introduced by Jay Kadane in 1984.
Kadane algorithm uses Dynamic Programming to solve the problems.
Kadane algorithm is used to solve the Maximum Subarray problem.
Maximum Subarray problem task is to find the contiguous subarray in a 1D array having the largest sum.
By using Kadane algorithmm the solution will be simple and efficient.
Working of Kadane algorithm:
Kadane algorithm we take 2 variables, max_so_far and current_sub_array_sum.
Iterate through the array and add each element to the current_sub_array_sum.
If the current_sub_array_sum become negative, then reset the current_sub_array_sum to 0 and discard any negative subarrays.
Update max_so_far seen so far whenever the current_sub_array_sum exceeds.
Now we are using the concept of optimal substructures, i.e each operation is calculated from a related smaller overlapping subproblem.
This algorithm can be seen as a simple example for DP.
Problem Statement:
You are given a 1D array, you need to find the maximum subarray su.
Example:
Input: arr[] = [1, 2, 3, 4, 5]Output: 15
Explanation:
The subarray [1, 2, 3, 4, 5] has contiguous sub array sum of 15.Solution Explanation:
as explained in the above algorithm working
Time Complexity: O(n)
Space Complexity: O(1)
Code Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSubarraySum(int arr[], int n) {
int max_so_far = 0;
int current_sub_array_sum = 0;
for (int i = 0; i < n; i++) {
current_sub_array_sum += arr[i];
if (current_sub_array_sum < 0) {
current_sub_array_sum = 0;
}
if (max_so_far < current_sub_array_sum) {
max_so_far = current_sub_array_sum;
}
}
return max_so_far;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSubarraySum(arr, n);
cout<< "Maximum subarray sum is = "<< max_sum;
return 0;
}
Output
Maximum subarray sum is = 15