Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6

    // C# program to print largest contiguous array sum 
    class Program
    {
        static int maxSubArraySum(int[] a)
        {
            int size = a.Length;
            int max_so_far = int.MinValue,
                max_ending_here = 0;

            for (int i = 0; i < size; i++)
            {
                max_ending_here = max_ending_here + a[i];

                if (max_so_far < max_ending_here)
                    max_so_far = max_ending_here;

                if (max_ending_here < 0)
                    max_ending_here = 0;
            }
            return max_so_far;
        }

        public static void Main()
        {
            int[] a = { -2,1,-3,4,-1,2,1,-5,4 };
            Console.Write("Maximum contiguous sum is " + maxSubArraySum(a));
            Console.ReadLine();
        }
    }

 

Output:

Maximum Subarray

 

Dry run:

  • i=0 and it’s value is -2
    max_ending_here=0+(-2)
    max_so_far=0 because max_ending_here is less than max_so_far
    max_ending_here = 0 because max_ending_here is less than 0
  • i=1 and it’s value is 1
    max_ending_here=0+(1)
    max_so_far=1 because max_ending_here is greater than max_so_far
    max_ending_here = 1
  • i=2 and it’s value is -3
    max_ending_here=1+(-3)
    max_so_far=1 because max_ending_here is less than max_so_far
    max_ending_here = 0  because max_ending_here is less than 0
  • i=3 and it’s value is 4
    max_ending_here=0+(4)
    max_so_far=4 because max_ending_here is greater than max_so_far
    max_ending_here = 4
  • i=4 and it’s value is -1
    max_ending_here=4+(-1)
    max_so_far=4 because max_ending_here is less than max_so_far
    max_ending_here = 3
  • i=5 and it’s value is 2
    max_ending_here=3+(2)
    max_so_far=5 because max_ending_here is greater than max_so_far
    max_ending_here = 5
  • i=6 and it’s value is 1
    max_ending_here=5+(1)
    max_so_far=6 because max_ending_here is greater than max_so_far
    max_ending_here = 6
  • i=7 and it’s value is -5
    max_ending_here=6+(-5)
    max_so_far=6 because max_ending_here is less than max_so_far
    max_ending_here = 1
  • i=8 and it’s value is 4
    max_ending_here=1+(4)
    max_so_far=6 because max_ending_here is less than max_so_far
    max_ending_here = 5

Leave a Reply

Your email address will not be published. Required fields are marked *