Sarbojit Basu
24BAI0187
Problem 5
Problem statement:
Maximum Subarray
Concept:
The Maximum Subarray problem is solved using Kadane’s Algorithm, which is a dynamic
programming technique that works by maintaining a running sum of elements in the array. At each
step, the algorithm decides whether to extend the current subarray or start a new subarray from the
current element, based on which choice gives a higher sum. By continuously updating the maximum
sum encountered so far, the algorithm efficiently finds the maximum possible subarray sum in a
single pass. This approach avoids unnecessary recomputation and achieves optimal performance.
Pseudocode:
Algorithm Maximum_Subarray(A[1…n])
Input:
A → array of integers
Output:
Maximum subarray sum
currentSum ← A[1]
maxSum ← A[1]
for i ← 2 to n
if currentSum < 0 then
currentSum ← A[i]
else
currentSum ← currentSum + A[i]
if currentSum > maxSum then
maxSum ← currentSum
Print maxSum
End Algorithm
Sarbojit Basu
24BAI0187
Code:
#include <stdio.h>
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter the elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
int maxSum = a[0];
int currentSum = a[0];
for (int i = 1; i < n; i++) {
if (currentSum < 0)
currentSum = a[i];
else
currentSum += a[i];
if (currentSum > maxSum)
maxSum = currentSum;
printf("Maximum Subarray Sum = %d\n", maxSum);
return 0;
}
Sarbojit Basu
24BAI0187
Output:
Time complexity:
The Maximum Subarray problem using Kadane’s Algorithm has a time complexity of O(n), where n is
the number of elements in the array. This is because the algorithm processes each element exactly
once in a single loop, performing only constant-time operations at each step. Since no nested loops
or additional passes are required, the solution is highly efficient and runs in linear time.