Advertisement
sylviapsh

Find the sequence of max sum in an array:Kadane Algorithm

Jan 9th, 2013
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.09 KB | None | 0 0
  1. using System;
  2. using System.Linq;
  3. class FindTheSequenceOfMaxSumInGivenArray
  4. {
  5.   static void Main()
  6.   {
  7.     //Write a program that finds the sequence of maximal sum in given array. Example:
  8.       //{2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4}
  9.       //Can you do it with only one loop (with single scan through the elements of the array)?
  10.     //Kadane's algorithm: http://en.wikipedia.org/wiki/Maximum_subarray_problem
  11.  
  12.  
  13.     int[] myArray = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 };
  14.     int currentSum = 0,
  15.         maxSum = int.MinValue, //minValue is needed for the arrays with negative numbers, otherwise 0 would be fine.
  16.         startIndex = 0,
  17.         maxStartIndex = 0,
  18.         maxEndIndex = 0;
  19.     if (Array.TrueForAll(myArray, x => x <= 0)) //Check if the whole array is negative, then the max elemnt would be the maximal sum
  20.     {
  21.       Console.WriteLine(myArray.Max());
  22.     }
  23.     else
  24.     {
  25.       for (int i = 0; i < myArray.Length; i++) //For the rest of the cases will sum the elements
  26.       {
  27.         currentSum += myArray[i];//On each iteration of the cycle we add the current element to the sum
  28.  
  29.         if (currentSum > maxSum)//Check if the sum has become greater than the maximal sum
  30.         {
  31.           maxSum = currentSum;
  32.           maxStartIndex = startIndex; //save the startIndex
  33.           maxEndIndex = i; //save the end index
  34.         }
  35.         if (currentSum < 0)
  36.         {
  37.           startIndex = i + 1; //If the sum goes below zero we start the sequence again be increasing the startIndex and reinitializing the sum
  38.           currentSum = 0;
  39.         }
  40.       }
  41.       //Print the output in a formatted way, e.g. {2, -1, 6, 4}
  42.       Console.Write("The sequence with maximal sum is: {");
  43.       for (int i = maxStartIndex; i <= maxEndIndex; i++)
  44.       {
  45.         if (i != maxEndIndex)
  46.         {
  47.           Console.Write("{0}, ", myArray[i]);
  48.         }
  49.         else
  50.         {
  51.           Console.Write("{0}", myArray[i]);
  52.           Console.WriteLine("}");
  53.         }
  54.       }
  55.       //Print the maximal sumy
  56.       Console.WriteLine("The maximal sum is {0}", maxSum);
  57.     }
  58.   }
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement