Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c#

.net

algorithm

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;
}
like image 901
k80sg Avatar asked Aug 23 '11 10:08

k80sg


People also ask

How do you find the largest Subarray in an array?

Simple Approach: Run a loop for i from 0 to n – 1, where n is the size of the array. Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax. Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.

What is the sum of its maximum subarray?

For arrays with no negative integers, the maximum subarray sum is the sum of the array in itself.

How do you find the largest sum of an array?

Find the Maximum subarray sum using Kadane' Algorithm. Keep that subarray intact and multiply the rest with -1. Considering the sum of the whole array as S, and the largest sum contiguous subarray as S1, the total sum will be equal to -(S-S1) + S1 = 2*S1 – S. This is the required sum.


2 Answers

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.

like image 159
Enigmativity Avatar answered Oct 08 '22 05:10

Enigmativity


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

like image 22
Mu Qiao Avatar answered Oct 08 '22 06:10

Mu Qiao