AspBucket offers ASP.NET, C#, VB, Jquery, CSS, Ajax, SQL tutorials. It is the best place for programmers to learn

Thursday 1 November 2018

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
  • [1,2]    = 3
  • [1,2,3] = 6
  • [2]       = 2
  • [2,3]    = 5
  • [3]       = 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;
        }

0 comments :

Post a Comment

  • Popular Posts
  • Comments