# AspBucket

## Kadane's Algorithm solution in c#

In the current article we are going to provide solution of the kadane's algorithm. Kadane's alogrithm is also known as "Maximum sub-array problem".

Problem Statement:
Given an array A[1, 2, 3, … n] containing both negative and positive integers. Find the contiguous sub-array with maximum sum.
Subarray A'[i, i + 1, i + 2, … j] where 1 ≤ i ≤ j ≤ n, where the sum of all the elements in A’ is maximum.

Example 1:[1,2,3]
Sub Array Combinations & their sum:

•        = 1
• [1,2]    = 3
• [1,2,3] = 6
•        = 2
• [2,3]    = 5
•        = 3
Hence the maximum sum of sub array is 6.

Example 2:[-1,-2,-3]
Sub Array Combinations & their sum:

• [-1]         = -1
• [-1,-2]     = -3
• [-1,-2,-3] = -6
• [-2]          = -2
• [-2,-3]      = -5
• [-3]          = -3
Hence the maximum sum of sub array is -1.

C# Solution

``` static int LongestSubSet(int[] arr)
{
int max_so_far = 0;
int max_ending_here = 0;

if (arr.OrderBy(p => p).Last() < 0)
return arr.OrderBy(p => p).Last();

for (int i = 0; i < arr.Length; i++)
{
max_ending_here += arr[i];

if (max_ending_here < 0) max_ending_here = 0;

if (max_ending_here > max_so_far)
max_so_far = max_ending_here;
}

return max_so_far;
}
```