Maximum Subarray Sum Using Kadane’s Algorithm
C
Hard
3 views
Problem Description
Find the subarray whose sum is maximum (Kadne's logic) - What is the intuition for resetting when the current sum is negative and why?
Official Solution
#include <stdio.h>
int main() {
int arr[100], n, i;
int currentSum = 0, maxSum;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:n");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
maxSum = arr[0];
for (i = 0; i < n; i++) {
currentSum += arr[i];
if (currentSum > maxSum) {
maxSum = currentSum;
}
if (currentSum < 0) {
currentSum = 0; // reset logic
}
}
printf("Maximum subarray sum = %dn", maxSum);
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!