Given an array of integers. Find the LARGEST subarray with the MAXIMUM sum

Question

Hi I am preparing for an interview code test and I stumbled across this question. I tried attempting it in C#, below is my embarrasing answer which I don't even know if it's right but mostly I guess not, could someone please kindly provide me with the answer so that when I rework on the solution I can at least have the answer to verify the output. Thanks.

Sample data:

int[] arr = {5, 1, -7, 3, 7};

Code:

int[] LargestsubarrayMaxSum(int[] arr)
{
    int temp = 0;
    int[] resultArr = new int[arr.Length];

    for (int i = 0; i < arr.Length - 1; i++)
    {
        if (i != 0)
        {
            foreach (int item in resultArr)
            {
                temp += item;
            }

            if (temp + arr[i + 1] > 0)
            {
                resultArr[i + 1] = temp + arr[i + 1];
            }
        }
        else
        {
            if ((arr[i] + arr[i + 1]) >= 0)
            {
                resultArr[i] = arr[i];
                resultArr[i + 1] = arr[i] + arr[i + 1];
            }
            else
            {
                resultArr[i] = arr[i];
                resultArr[i + 1] = 0;
            }
        }
    }
    return resultArr;
}

Solution 1

How about this?

var arr = new [] {5, 1, -7, 3, 7};

var xs =
    from n in Enumerable.Range(0, arr.Length)
    from l in Enumerable.Range(1, arr.Length - n)
    let subseq = arr.Skip(n).Take(l)
    orderby subseq.Count() descending
    orderby subseq.Sum() descending
    select subseq;

var maxSumSubseq = xs.First();

EDIT: Added orderby subseq.Count() descending to get maximal length subsequence.

---

EDIT: Added explanation as per comment.

1. Select all possible subsequence starting indices:

   from n in Enumerable.Range(0, arr.Length)
   

2. Select all possible lengths of subsequences given the starting index:

   from l in Enumerable.Range(1, arr.Length - n)
   

3. Extract the subsequence from the array:

   let subseq = arr.Skip(n).Take(l)
   

4. Order subsequences by descending length (i.e. longest first) - could order by l instead of subseq.Count() but the latter is more expressive even though the former is more efficient:

   orderby subseq.Count() descending
   

5. Calculate the sum of each subsequence and order the subsequences so highest valued sums are first:

   orderby subseq.Sum() descending
   

6. Select the subsequences:

   select subseq;
   

7. Only select the first subsequence - it's the highest value sum with the greatest length:

   xs.First();
   

Hope this helps.

Solution 2

O(N) time complexity and O(1) space complexity. This is the optimal solution I know:

#include <stdio.h>
#include <limits.h>

int get_max_sum(int* array, int len, int* start, int* end)
{
    int max_sum = INT_MIN, sum = 0, i;
    int tmp_start = 0;

    for(i = 0; i != len; ++i)
    {
        sum += array[i];

        // if the sum is equal, choose the one with more elements
        if(sum > max_sum || (sum == max_sum && (end - start) < (i - tmp_start)))
        {
            max_sum = sum;
            *start = tmp_start;
            *end = i;
        }
        if(sum < 0)
        {
            sum = 0;
            tmp_start = i + 1;
        }
    }

    return max_sum;
}

Here are some test cases:

int main(int argc, char **argv)
{
    int arr1[] = {5, 1, -7, 3, 7};
    int arr2[] = {1};
    int arr3[] = {-1, -7, -3, -7};
    int arr4[] = {5, 1, -7, 2, 2, 2};
    int start, end, sum;

    sum = get_max_sum(arr1, 5, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    sum = get_max_sum(arr2, 1, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    sum = get_max_sum(arr3, 4, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    sum = get_max_sum(arr4, 6, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    return 0;
}

$ ./a.out
sum: 10, start: 3, end: 4
sum: 1, start: 0, end: 0
sum: -1, start: 0, end: 0
sum: 6, start: 3, end: 5

Update1: Added code to print the index of the subarray.

Update2: If two sub arrays with the same sum are found, choose the one with more elements.

Update3: Fix the algorithm for leading negative numbers

Solution 3

You could either use Enigmativity's answer but add the extra order by of subseq.Count() descending

or if you want an insane linq query......

int[] arr = .......

var result = new[]{0}
             .Concat(arr.Select((x,i)=>new {x,i})
             .Where(a=>a.x<0).Select(a=>a.i+1))
             .Select (i => arr.Skip(i).TakeWhile(a => a>=0))
             .OrderByDescending(a=>a.Sum())
             .OrderByDescending(a=>a.Count()).First();

However usually you want to do these as a single loop..

var result=new List<int>();
var maxResult=new List<int>();

// These next four variables could be calculated on the fly 
// but this way prevents reiterating the list each loop.
var count=0; 
var sum=0;
var maxCount=0;
var maxSum=0;

foreach (var value in arr) {
  if (value >=0) {
    result.Add(value);
    sum+=value;
    count++;
  } else {
    if (sum>maxSum || (sum==maxSum && count>maxCount)) {
      maxSum=sum;
      maxCount=count;
      maxResult=result;
    }
    result.Clear();
    count=0;
    sum=0;
  }
}

var returnValue=maxResult.ToArray();

Solution 4

    public static int[] FindMaxArrayEx(int[] srcArray)
    {
        int[] maxArray = new int[1];
        int maxTotal = int.MinValue;
        int curIndex = 0;
        int tmpTotal = 0;
        List<int> tmpArray = new List<int>();

        if (srcArray.Length != 1)
        {
            for (int i = 0; i < srcArray.Length; i++)
            {
                tmpTotal = 0;
                curIndex = i;
                tmpArray.Clear();

                while (curIndex < srcArray.Length)
                {
                    tmpTotal += srcArray[curIndex];
                    tmpArray.Add(srcArray[curIndex]);

                    if (tmpTotal > maxTotal)
                    {
                        maxTotal = tmpTotal;
                        maxArray = tmpArray.ToArray();
                    }

                    curIndex++;
                }
            }
        }
        else
        {
            maxTotal = srcArray[0];
            maxArray = srcArray;
        }

        Console.WriteLine("FindMaxArrayEx: {0}",maxTotal);

        return maxArray;

    }

Solution 5

Here is a totally working solution:

using System;
using System.Collections.Generic;

class MaxSumOfSubArray
{
    static void Main()
    {
        //int[] array = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 };
        //maxSubSum(array);

        int digits;
        List<int> array = new List<int>();
        Console.WriteLine("Please enter array of integer values. To exit, enter eny key different than 0..9");

        while (int.TryParse(Console.ReadLine(), out digits))
        {
            array.Add(digits);
        }

        maxSubSum(array);
    }

    public static void maxSubSum(List<int> arr)
    {
        int maxSum = 0;
        int currentSum = 0;
        int i = 0;
        int j = 0;
        int seqStart=0;
        int seqEnd=0;
        while (j < arr.Count)
        {
            currentSum = currentSum + arr[j];

            if (currentSum > maxSum)
            {
                maxSum = currentSum;
                seqStart = i;
                seqEnd = j;
            }
            else if (currentSum < 0)
            {
                i = j + 1;
                currentSum = 0;
            }
            j++;
        }
        Console.Write("The sequence of maximal sum in given array is: {");
        for (int seq = seqStart; seq <= seqEnd; seq++)
        {
            Console.Write(arr[seq] + " ");
        }
        Console.WriteLine("\b}");
        Console.WriteLine("The maximum sum of subarray is: {0}", maxSum);
    }
}

View more solutions

Comments

[Bob Vale]

can't guarantee that this result will give you the right answer for var arr = new [] {5,1,-7,2,2,2}

[Lieven Keersmaekers]

+1 For all the variations I've tried, it returned the correct result but you might want to explain one another. I have no idea how this works.

[Enigmativity]

@Lieven - I added an explanation of each line. Let me know if this helps or not. Cheers.