Given an array of unsorted positive and negative values of size N. For example [

ID: 3817980 • Letter: G

Question

Given an array of unsorted positive and negative values of size N. For example [10, 20, -5, -15, 11, -4, -30, 25, …]. We need to find the two indexes i, and j where the sum of the values between these two indexes (inclusive) is the largest.

That is, denote by Sum[i,j] the sum of the values between i, j (inclusive), and we want the indexes where there “Sum[]” is the largest.

Write a pseudocode for an algorithm to solve the problem above in O(N). In this question, you only need to sketch the algorithm and analyze it to show it is O(N) time complexity.

Explanation / Answer

This is basically Kadance Alorithm

Thsi algorithm is looping over array only once and doing constant amount of time in each iteration and hence Time complexity is O(N)

Here is code in C++ printing indices

// C++ program to print largest contiguous array sum

#include<iostream>

#include<climits>

using namespace std;

int maxSubArraySum(int a[], int size)

{

int max_so_far = INT_MIN, max_ending_here = 0,

start =0, end = 0, s=0;

for (int i=0; i< size; i++ )

{

max_ending_here += a[i];

if (max_so_far < max_ending_here)

{

max_so_far = max_ending_here;

start = s;

end = i;

}

if (max_ending_here < 0)

{

max_ending_here = 0;

s = i+1;

}

cout << "Maximum contiguous sum is "

<< max_so_far << endl;

cout << "Starting index "<< start

<< endl << "Ending index "<< end << endl;

}

/*Driver program to test maxSubArraySum*/

int main()

{

int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};

int n = sizeof(a)/sizeof(a[0]);

int max_sum = maxSubArraySum(a, n);

return 0;

}