SHARE
TWEET

Arrays - 08_SequenceOfMaximalSum

ntodorova Jan 18th, 2013 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2.  
  3. /*
  4.  * 8. Write a program that finds the sequence of maximal sum in given array.
  5.  * Example: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4}
  6.  * Can you do it with only one loop (with single scan through the elements of the array)?
  7.  */
  8. class SequenceOfMaximalSum
  9. {
  10.         static void Main()
  11.         {
  12.                 int[] arr = { 3, 2, 7, 4, 5, 18, 4, 54, 32 };
  13.  
  14.                 int maxTemp = int.MinValue;
  15.                 int maxEnd = 0;
  16.                 int start = 0;
  17.                 int startTemp = 0;
  18.                 int end = 0;
  19.  
  20.                 for (int i = 0; i < arr.Length; i++)
  21.                 {
  22.                         maxEnd += arr[i];
  23.  
  24.                         if (arr[i] > maxEnd)
  25.                         {
  26.                                 maxEnd = arr[i];
  27.                                 startTemp = i;
  28.                         }
  29.                         if (maxEnd > maxTemp)
  30.                         {
  31.                                 maxTemp = maxEnd;
  32.                                 start = startTemp;
  33.                                 end = i;
  34.                         }
  35.                 }
  36.  
  37.                 Console.WriteLine("Maximal sum is: {0}", maxTemp);
  38.  
  39.                 for (int j = start; j <= end; j++)
  40.                 {
  41.                         Console.Write(arr[j] + " ");
  42.                 }
  43.         }
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top