Find an algorithm to find the largest sum subarray in an array of integers. (Better than O(n^2) ).

Question

Sumer Cip · Accepted Answer

See Kadane's Algorithm.

Tanin · Answer

It shouldn't be that complicated.

A dynamic programming can solve it easily with O(n)

Volodymyr · Answer

A dynamic programming can solve it with O(n). 
On the i-th step save inclusive and exclusive values with the next logic (A - input array):
Inclusive(i) = Max(Inclusive(i-1), 0) + A[i]
Exclusive(i) = Max(Inclusive(i-1), Exclusive(i-1))

C# example:

class Item
{
    public int Inclusive { get; set; }
    public int Exclusive { get; set; }
}

int[] input = new int[] {-3, 15, -10, 1, 5, 5, -15, 17};

Item prev = new Item
                {
                    Inclusive = input[0],
                    Exclusive = 0
                };

for (int i = 1; i < input.Length; i++)
{
    Item curr = new Item
                    {
                        Inclusive = Math.Max(prev.Inclusive, 0) + input[i],
                        Exclusive = Math.Max(prev.Inclusive, prev.Exclusive)
                    };
    prev = curr;
}

Console.WriteLine(Math.Max(prev.Inclusive, prev.Exclusive));
Console.ReadKey();

sundaram · Answer

int maxSum(vector& S) {
    int max_sum = 0;
    int current_sum = 0;
    int positive = 0;

    for (size_t i = 0; i  max_sum) {
        max_sum = current_sum;
    }
    if (positive) {
        return max_sum;
    }
    return -1;  // return -1 if there is no positive set
}

Dave · Answer

public static void findLargestSumSubArray(int[] arr){
		if(arr == null) {
			System.out.println("NULL ARRAY");
		}
		else if(arr.length == 1){
			SortingFun.printArray(arr);
		}
		else{
			int maxSum = 0;					//the largest sub array sum so far
			int maxStart = -1;				//start of the sub array with largest sum
			int maxEnd = -1;				//end of the sub array with largest sum
			int largestNegativeVal = Integer.MIN_VALUE;	//the smallest negative number so far
			
			int runStart = -1;				//start of a run (a run starts with a positive number)
			int sum = 0;					//the sum in the current run
			int i = 0;						//runner index
			
			while(i  largestNegativeVal){
					largestNegativeVal = val;
				}
				
				//if it's a positive value and we are not in a run yet, set i as the start of a run
				if(val > 0 && runStart == -1) runStart = i;
				
				sum += val;
				
				//if the current value causes the sum to become negative, discard the sub array before i
				if(sum = 0){
						int k = i;
						while(arr[k]  maxSum){
							maxSum = sum;
							maxStart = runStart;
							maxEnd = k;
						}
					}
					
					//reset run-related variables
					runStart = -1;
					sum = 0;
				}
				
				i++;
			}//end while
			
			//if we are still in a run, then discard all the trailing negative numbers. if the sum of the rum without
			//trailing negative numbers is larger than the current max, update current max
			if(runStart >= 0){
				i--;
				while(arr[i]  maxSum){
					maxSum = sum;
					maxStart = runStart;
					maxEnd = i;
				}
			}
			
			if(maxStart >= 0){
				SortingFun.printArray(Arrays.copyOfRange(arr, maxStart, maxEnd + 1));
			}
			else{
				int[] temp = new int[1];
				temp[0] = largestNegativeVal;
				SortingFun.printArray(temp);
			}
		}
		
	}

Aditya · Answer

def LargestSumSubArray(arr):
    sum	= max_sum = 0
    low_end = high_end = 0
    tmp_low_end = 0
    for i, a in enumerate(arr):
        sum += a
	print 'sum = %d max_sum = %d' %	(sum, max_sum)
        if sum > max_sum:
            max_sum = sum
            high_end = i
            if tmp_low_end:
		low_end	= tmp_low_end
        else:
            if a >= 0:
		if a > max_sum:
                    low_end = high_end = i
		    max_sum = sum = a
		else:
                    sum	= a
                    tmp_low_end	= i

    print '%d %d' % (low_end, high_end)
    return arr[low_end:high_end + 1]

Sem · Answer

//find the largest sum subarray in an array of integers. (Better than O(n^2) ).
//				0	1	2	  3		4		   5		6	  7	  8	  9	  10	11	 	12
$input = array(12, -23, 123, 12, 213123123, -23432, 1231231, 12, 12, 12, -34, -23423, 2123);
$len = count($input);
$temp = ls($input, 0, $len - 1);

function ls($input, $start, $end) {
	if ($start == $end) {
		return array($input[$start], $start, $end);
	} else {
		$out = ls($input, $start, $end - 1);
		$lmax = $max = $out[0];
		$i = $out[1];
		$j = $out[2];
		
		$sum = 0;
		for ($index = $end; $index > $out[2]; $index--) {
			$sum += $input[$index];
			if ($sum > $lmax) {
				$lmax = $sum;
				$i = $index;
				$j = $end;
			}
		}
		
		$sum += $max;
		if ($sum > $lmax) {
			$max = $sum;
			$i = $out[1];
			$j = $end;
		} else {
			$max = $lmax;
		}
		
		return array($max, $i, $j);
	}
}

Tom · Answer

depends on your definition, if it must be continuous, then DP, O(n) #include #include #include using namespace std; int main() { int input[9999]; int inputL = 0; while (true) { cin >> input[inputL]; if (999 == input[inputL]) break; inputL++; } for (int i = 1; i 0) input[i] += input[i-1]; int max = 0; for (int i = 0; i < inputL; i++) if (max < input[i]) max = input[i]; cout << max << endl; return 0; } /* -2 1 -3 4 -1 2 1 -5 4 999 -1 -41 -51 -5 -2 999 -1 0 999 0 999 1 0 2 -3 5 5 -5 999 */ otherwise simply scan, pick the positive ones, O(n)

Balaprasath Rajan · Answer

Sort the array. 

{1,5,3,7,2,9}

{1,2,3,5,7,9}

Then largest  sum can be given by {2,3,5,7,9} - leave a[0] :-)

Anon · Answer

Sort the array in n log(n) and then start adding from right to left until the sum drops and thats your largest sum.

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas