Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Linq;
- class FindTheSequenceOfMaxSumInGivenArray
- {
- static void Main()
- {
- //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}
- //Can you do it with only one loop (with single scan through the elements of the array)?
- //Kadane's algorithm: http://en.wikipedia.org/wiki/Maximum_subarray_problem
- int[] myArray = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 };
- int currentSum = 0,
- maxSum = int.MinValue, //minValue is needed for the arrays with negative numbers, otherwise 0 would be fine.
- startIndex = 0,
- maxStartIndex = 0,
- maxEndIndex = 0;
- if (Array.TrueForAll(myArray, x => x <= 0)) //Check if the whole array is negative, then the max elemnt would be the maximal sum
- {
- Console.WriteLine(myArray.Max());
- }
- else
- {
- for (int i = 0; i < myArray.Length; i++) //For the rest of the cases will sum the elements
- {
- currentSum += myArray[i];//On each iteration of the cycle we add the current element to the sum
- if (currentSum > maxSum)//Check if the sum has become greater than the maximal sum
- {
- maxSum = currentSum;
- maxStartIndex = startIndex; //save the startIndex
- maxEndIndex = i; //save the end index
- }
- if (currentSum < 0)
- {
- startIndex = i + 1; //If the sum goes below zero we start the sequence again be increasing the startIndex and reinitializing the sum
- currentSum = 0;
- }
- }
- //Print the output in a formatted way, e.g. {2, -1, 6, 4}
- Console.Write("The sequence with maximal sum is: {");
- for (int i = maxStartIndex; i <= maxEndIndex; i++)
- {
- if (i != maxEndIndex)
- {
- Console.Write("{0}, ", myArray[i]);
- }
- else
- {
- Console.Write("{0}", myArray[i]);
- Console.WriteLine("}");
- }
- }
- //Print the maximal sumy
- Console.WriteLine("The maximal sum is {0}", maxSum);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement