How to find the longest subarray with the largest sum in an array in O(N) time ?

Question

Expected Time Complexity : O(N) , where 'N'  is the size of array .

-1000000<=A[i]<=1000000

1<=N<=100000

Example :

5 10 -100 -200 15

 

Output : Subarrays with largest sums are {5,10}    and {15} . But {5,10} has the largest size of 2 . Hence our answer is  2 .

Answer 1

ALGORITHM

1. kadane's algorithm + count == stack stimulation
   
   initlize variables
   mxSum     = minimum possible value , as numbers can be all negative
   mxCt    = max count, our answer
   sum        = running sum 
   ct        = running count

2. ALGO BEGINS HERE
   start traversing form the begning of the array
       if our current sum is less then zero
           - set currSum = currentElement
           - count as 1 (as we are count this current element)
       else
           - add current element to the sum
           - increase the count
           
       if our currSum is greater then or equal to currentGlobalMaxSum
           if currSum > currentGlobalMaxSum then 
               set mxCt to currCount
           else
               set mxCt to maximum of ( mxCt and currCount )
               
           set currentGlobalMaxSum to currSum
   print the answers

 

C++ CODE begins here

int32_t main()

{

    vector<int64_t> tc1 = {15,-100,-20,10,5,-100,5,5,5,-10000};

    vector<int64_t> tc2 = {-100,5,5,5,5,-10000,50000};

    vector<int64_t> tc3 = {-8,-2,-4,-6,-1,-8,-9,-2,-3,-4};


    vector<int64_t> a = tc1;


    int64_t mxSum = LONG_MIN , mxCt = 0 , sum = 0 , ct = 0;


    for(auto i : a)

    {

        if(sum < 0)

            sum = i,

            ct = 1;

        else

            sum += i,

            ct++;


        if(sum >= mxSum)

            {

                mxCt = (sum > mxSum) ? ct : max(ct , mxCt);

                mxSum = sum;

            }

    }

    cout<<"Max Sum is "<<mxSum<<" "<<"Max len is "<<mxCt;

}

INPUT-TC1

15  -100  -20  10  5  -100  5  5  5  -10000

OUTPUT-TC1

Max Sum is 15 Max len is 3


INPUT-TC2

-100  5  5  5  5  -10000  50000

OUTPUT-TC2

Max Sum is 50000 Max len is 1


INPUT-TC3

-8  -2  -4  -6  -1  -8  -9  -2  -3  -4

OUTPUT-TC3

Max Sum is -1 Max len is 1

- do let me know if its wrong, special case handling, or can be improved

Answer 2

Given an array of integers, find the sum of a continuous sub-array with the largest sum.
Example:
Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

To solve it efficiently we can use Kadane's Algorithm

Pseudo code

1.Initialize maxsum = 0 , sumsofar= a[0]

2.for I =0 to arr.size

maxsum = maxsum + a[i]

if maxsum < sumoffar

Maxsum = sumsofar

if sumsofar < 0

Maxsum =0

Then finally I will return maxsum

Reason why I had used this approach As I'll choose first array element as max and maintain a sum then I'll will add one by one element in sum and will check if my max is less than sum if so I'll overwrite my max by sum and if my sum is less than 0, I would make my sum as 0 as it's of not use to use add another element to sum which is less than 0.

 

 

Comments

I think your alogo works for max sum in an array but the question is different.

---

Yes my algorithm will work for max sum in an array.
Actually I hadn't read the whole questions just read the largest sum in  an array .
Thanks for going to my post.
From the next time onward I'll make sure that I'm going through the question twice before posting any solution.