-
Complete the code below to efficiently find a (continuous) sub-array with the greatest sum from the integer array passed in to the constructor. For example, the array {1, 3, 5, -10, 10, 3, -15, 12} has a sub-array with a sum of 13 that starts at position 4 (starting from 0) and ends at position 5: {10, 3}. Alternately, the array {4, -3, 8, -2, -6, 5} has a sub-array with sum 9 that starts at 0 and ends at 2: {4, -3, 8}. (See if you can do it in linear time, i.e. only make a single loop through the array.)
namespace Test
{
///
/// Summary description for Class1.
///
public class GreatestSubArray
{
private int start;
private int end;
private int sum;
public int Start
{
get { return start; }
}
public int End
{
get { return end; }
}
public int Sum
{
get { return sum; }
}
public GreatestSubArray(int[] arr)
{
// TODO: implement algorithm finding
// subarray with the maximal sum
}
}
}
2.Write a NUnit test to verify that the algorithm above works.
Ryan AlfordPosted Mar 20, 2009, 12:07 PM