SHARE
TWEET

C# Part II Arrays Exercise 8

TanyaPetkova Dec 21st, 2013 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Write a program that finds the sequence of maximal sum in given array. Example:{2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4}
  2. //Can you do it with only one loop (with single scan through the elements of the array)?
  3.  
  4. using System;
  5.  
  6. class SequenceOfMaxSum
  7. {
  8.     static void Main()
  9.     {
  10.         int arrayLength;
  11.  
  12.         Console.Write("Enter the array's length: ");
  13.  
  14.         while (!int.TryParse(Console.ReadLine(), out arrayLength) || arrayLength <= 0)
  15.         {
  16.             Console.Write("Invalid input. Enter a positive integer number: ");
  17.         }
  18.  
  19.         int[] array = new int[arrayLength];
  20.  
  21.         for (int i = 0; i < arrayLength; i++)
  22.         {
  23.             Console.Write("Enter the {0} element of the  array: ", i);
  24.  
  25.             while (!int.TryParse(Console.ReadLine(), out array[i]))
  26.             {
  27.                 Console.Write("Invalid input. Enter an integer number: ");
  28.             }
  29.         }
  30.  
  31.         int maxSum = array[0];
  32.         int currentSum = array[0];
  33.         int startIndex = 0;
  34.         int endIndex = 0;
  35.         int bestStart = startIndex;
  36.         int bestEnd = endIndex;
  37.  
  38.         for (int i = 1; i < array.Length; i++)
  39.         {
  40.             if (currentSum > 0)
  41.             {
  42.                 if (currentSum > maxSum)
  43.                 {
  44.                     maxSum = currentSum;
  45.                     bestStart = startIndex;
  46.                     endIndex = i;
  47.                     bestEnd = endIndex;
  48.                 }
  49.                 currentSum += array[i];
  50.             }
  51.             else
  52.             {
  53.                 currentSum = array[i];
  54.                 startIndex = i;
  55.                 endIndex = i;
  56.             }
  57.         }
  58.  
  59.         if (currentSum > maxSum)
  60.         {
  61.             maxSum = currentSum;
  62.             bestStart = startIndex;
  63.             bestEnd = array.Length;
  64.         }
  65.  
  66.         int[] maxSequence = new int[bestEnd - bestStart];
  67.  
  68.         for (int i = bestStart, j = 0; i < bestEnd; i++, j++)
  69.         {
  70.             maxSequence[j] = array[i];
  71.         }
  72.  
  73.         Console.WriteLine("The sequence {0} has maximal sum {1}.", string.Join(", ", maxSequence), maxSum);
  74.     }
  75. }
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