arachnode.net
An Open Source C# web crawler with Lucene.NET search using SQL Server 2008/2012/2014/2016/CE An Open Source C# web crawler with Lucene.NET search using MongoDB/RavenDB/Hadoop
Search the Live Index Does arachnode.net scale? | Download the latest release
Programming Challenge 2

Question:  You are given an array of n integers (both positive and negative).  Find the first continuous sequence of integers with the largest sum.

Example 1: Input: {-7, 4, -2, 5, 3, -6, 8, -9} : Answer: {4, -2, 5, 3, -6, 8}

Example 2: Input {5, -3, -4, -2, 6, -4, 1, 3} : Answer: {6}

Answer:

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

namespace Interview2
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input1 = new int[] { -7, 4, -2, 5, 3, -6, 8, -9 };

            int[] largestSumSequence = GetLargestSumSequence(input1);

            int[] input2 = new int[] { 5, -3, -4, -2, 6, -4, 1, 3 };

            largestSumSequence = GetLargestSumSequence(input2);
        }

        static int[] GetLargestSumSequence(int[] input)
        {
            if (input.Length == 0)
            {
                return null;
            }

            int maximumSum = int.MinValue;
            int currentSum;

            int maximumSumI = 0;
            int maximumSumJ = 0;

            for (int i = 0; i < input.Length; i++)
            {
                currentSum = input[ i ];

                //i don't really like this repeated code... :(
                if (currentSum > maximumSum)
                {
                    maximumSum = currentSum;

                    maximumSumI = i;
                    maximumSumJ = i;
                }

                for (int j = i + 1; j < input.Length; j++)
                {
                    currentSum += input[j];

                    //i don't really like this repeated code... :(
                    if (currentSum > maximumSum)
                    {
                        maximumSum = currentSum;

                        maximumSumI = i;
                        maximumSumJ = j;
                    }   
                }
            }

            int[] largestSumSequence = new int[maximumSumJ - maximumSumI + 1];

            for (int i = 0, j = maximumSumI; j <= maximumSumJ; i++, j++)
            {
                largestSumSequence[ i ] = input[j];
            }

            return largestSumSequence;
        }
    }
}

Posted Thu, Feb 7 2013 11:05 AM by arachnode.net
An Open Source C# web crawler with Lucene.NET search using SQL 2008/2012/CE

copyright 2004-2017, arachnode.net LLC