The Kadane's algorithm is used to find the maximum subarray
sum in an array of integers. It is an efficient algorithm with a time
complexity of O(n), where n is the size of the array. Here's an implementation
of the Kadane's algorithm in C#:
using System;
class Program
{
static int KadaneAlgorithm(int[] nums)
{
int currentSum = nums[0]; // Tracks the sum of the current subarray
int maxSum = nums[0]; // Tracks the maximum sum found so far
for (int i = 1; i < nums.Length; i++)
{
// Extend the current subarray or start a new subarray
//from the current element
currentSum = Math.Max(nums[i], currentSum + nums[i]);
// Update the maximum sum if the current sum is greater
maxSum = Math.Max(maxSum, currentSum);
}
return maxSum;
}
static void Main()
{
int[] nums = { -2, -3, 4, -1, -2, 1, 5, -3 };
int maxSum = KadaneAlgorithm(nums);
Console.WriteLine("Maximum subarray sum: " + maxSum);
}
}
In the above example, we define the KadaneAlgorithm function that takes an
array of integers (nums) as input and returns the maximum subarray sum. We
initialize currentSum and maxSum with the first element of the array.
We then iterate over the remaining elements of the array,
starting from index 1. At each step, we update currentSum by taking the maximum
of the current element or the sum of the current element and the previous
currentSum. This allows us to extend the current subarray or start a new
subarray from the current element.
We also update maxSum by taking the maximum of the current
maxSum and the updated currentSum. This ensures that we keep track of the
maximum sum found so far.
After the loop, we return the maxSum, which represents the
maximum subarray sum.
In the Main method, we provide a sample array nums and call the KadaneAlgorithm function to find the maximum subarray sum. The result is then printed to the console.
