SHARE
TWEET

Sequence with max sum

a guest Dec 15th, 2013 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //08. Write a program that finds the sequence of maximal sum in given array.
  2. //    Example: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  {2, -1, 6, 4}
  3.  
  4. using System;
  5.  
  6. namespace Sequence_Of_Maximal_Sum
  7. {
  8.     class Sequence_Of_Maximal_Sum
  9.     {
  10.         static void Main()
  11.         {
  12.             Console.Write("n = ");
  13.             int n = int.Parse(Console.ReadLine());
  14.             int[] arr = new int[n];
  15.  
  16.             Console.WriteLine("Enter the elements: ");
  17.             for (int i = 0; i < n; i++)
  18.             {
  19.                 arr[i] = int.Parse(Console.ReadLine());
  20.             }
  21.  
  22.             //For testing:
  23.             //int[] arr = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 };
  24.  
  25.             int maxSum = 0;
  26.             int sum = 0;
  27.             int startedPos = 0;
  28.             int endedPos = 0;
  29.  
  30.             for (int i = 0; i < arr.Length; i++)
  31.             {
  32.                 for (int j = i + 1; j < arr.Length; j++)
  33.                 {
  34.                     for (int k = i; k <= j; k++)
  35.                     {
  36.                         sum += arr[k];
  37.                     }
  38.  
  39.                     if (sum > maxSum)
  40.                     {
  41.                         maxSum = sum;
  42.                         startedPos = i;
  43.                         endedPos = j;
  44.                     }
  45.  
  46.                     sum = 0;
  47.                 }
  48.             }
  49.  
  50.             Console.WriteLine("The sequence with maximal sum is:");
  51.             for (int i = startedPos; i <= endedPos; i++)
  52.             {
  53.                 Console.Write("{0} ", arr[i]);
  54.             }
  55.             Console.WriteLine();
  56.             Console.WriteLine("And its sum is {0}", maxSum);
  57.  
  58.             //==========================================================================================================
  59.             //The Kadane's way with one loop:
  60.  
  61.             //int sum = arr[0], maxSum = arr[0];
  62.  
  63.             //int begin = 0;
  64.             //int begin_temp = 0;
  65.             //int end = 0;
  66.  
  67.             //for (int i = 1; i < arr.Length; i++)
  68.             //{
  69.             //    if (maxSum < 0)
  70.             //    {
  71.             //        maxSum = arr[i];
  72.  
  73.             //        begin_temp = i;
  74.             //    }
  75.             //    else
  76.             //    {
  77.             //        maxSum += arr[i];
  78.             //    }
  79.  
  80.             //    if (maxSum >= sum)
  81.             //    {
  82.             //        sum = maxSum;
  83.  
  84.             //        begin = begin_temp;
  85.             //        end = i;
  86.             //    }
  87.             //}
  88.  
  89.             //Console.WriteLine("The maximal sum in sequence is {0}\nAnd its sequence is:", maxSum);
  90.  
  91.             //for (int i = begin; i <= end; i++)
  92.             //{
  93.             //    Console.Write("{0} ", arr[i]);
  94.             //}
  95.  
  96.             //Console.WriteLine();
  97.         }
  98.     }
  99. }
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