using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
	class Program
	{
		static void Main(string[] args)
		{
			int[] array = new int[] { 1, -12, 143, 14, -1000, 800, 7, -8, 11 };
			Console.WriteLine("Sending this array");
			WriteArray(array);
			Console.WriteLine("Reply is:");
			WriteArray(FindHighestSubset(array));


			array = new int[] { 2, -1, 5000, -10000, 1000, -200, 5000, -8, 11 };
			Console.WriteLine("Sending this array");
			WriteArray(array);
			Console.WriteLine("Reply is:");
			WriteArray(FindHighestSubset(array));

			Console.WriteLine("Press <ENTER> to exit");
			Console.ReadLine();
		}

		private static void WriteArray(int[] array)
		{
			Console.WriteLine("Writing array");
			for (int i = 0; i < array.Length; i++)
			{
				Console.WriteLine(array[i]);
			}
			Console.WriteLine("End writing array");
		}

		private static int[] FindHighestSubset(int[] array)
		{
			int count = 0;
			int length = 0;
			int bestCount = 0;
			int bestStart = 0;
			int bestLength = 0;
			int startPos = 0;

			for (int i = 0; i < array.Length; i++)
			{
				// extract the value
				int value = array[i];
				// see if it is a new start point
				if (value > 0 && count == 0)
				{
					startPos = i;
				}
				// check what the value will become if added
				int tempCount = count + value;
				// hmmm it's less than zero
				if (tempCount < 0)
				{
					// if our count thus far is the best then save the data
					if (count > bestCount)
					{
						bestCount = count;
						bestStart = startPos;
						bestLength = length;
						// reset the count and length
						count = 0;
						length = 0;
					}
				}
				else
				{
					count = tempCount;
					length++;
				}
			}

			// check the last count
			if (count > bestCount)
			{
				bestCount = count;
				bestStart = startPos;
				bestLength = length;
				// reset the count and length
				count = 0;
				length = 0;
			}

			// create our new array and copy the subset and return it
			int[] toReturn = new int[bestLength];
			Array.Copy(array, bestStart, toReturn, 0, toReturn.Length);
			return toReturn;
		}
	}
}