1 like 0 dislike
256 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 .
| 256 views

1 like 0 dislike

## 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

```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
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.