1 like 0 dislike
351 views
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 .
in Algorithms and Problems by Expert (17,730 points) | 351 views

2 Answers

1 like 0 dislike
Best answer

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

by Expert (1,790 points)
selected by
1 like 0 dislike
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.

 

 

by Expert (720 points)
0 0
I think your alogo works for max sum in an array but the question is different.
0 0
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.