Master data structures and algorithms for coding interviews at algomap.io :)
GregHogg
Am I missing something, but you didn’t complete the challenge. You’re just returning the max sum, not the array that created the max sum.
michaelstump
You can also solve it using divide and conquer:
There are three possibilities:
1. The maximum subarray is entirely within the left half.
2. The maximum subarray is entirely within the right half.
3. The maximum subarray crosses the middle i.e. starts in the left half and ends in the right half.
Solve the first two cases recursively, the last case can be solved in O(1) by utilizing the recursive calls and the time complexity will be T(n) = 2*T(n/2) + O(1) which is in O(n)
For each recursive call, return:
The maximum subarray for the current segment, the total sum of the current segment, the maximum prefix sum of the current segment, and the maximum suffix sum of the current segment.
With this, you can calculate the maximum subarray in each half, the maximum subarray that crosses the middle and the total sum of the array, the maximum prefix sum, and the maximum suffix sum. The time complexity is O(n)
galdali
This is basically greedy. Keep expanding the subarray until it reaches 0 or less. If 0 or less, start a new subarray from the next element. In the meanwhile the max sum is updated every step.
xiahualiu
If all the elements were negative this would give the wrong answer right?
RobMartin-gzzk
Is this kadens algorithm if im wrong pls correct me
vivekvardhanreddy
Can I know what is the app you use for drawing?
Bsusuaa
What if all numbers are negative? Your solution would return 0 but rather it should return single element which is maximum of all negative number
pavangupta
Like make
sum=0
max=Integer.MIN_VALUE
Traverse our for loop i=0 ->nums.length;i++
sum+=nums[i]
And if(sum>max) max=sum
And if sum is negative return 0
And finally return max
ChiragSharma-pbrg
Essentially any future elements can only improve our cause
Either by increasing the sum of or by allowing us to ditch the dead weight and start from scratch
Hence why it only needs one pass through the list
Really neat. Wouldn’t have believed it at first glance tho
quesostuff
Bro can you make sorts on OOPS based questions ??
utkarshpandey
We can use sort and then new arry we can add len -1 sum .
Didn't we get the same results in that
waleedabdullah
"Find the subarray that has the maximum sum"
*Finds the maximum sum*
No, I have not found a coding job yet
