The Problem
Solution using greedy algorithm:
The problem asks us to find the contiguous subarray that contains the maximum sum and return this sum.
So, the input is a linear array and that what makes it maybe it can be solved using greedy algorithm.
So what is the idea here we need at each step to check what is the optimal solution for the current step and pick it up and when we reach the end we will have the general optimal solution for our problem?
In steps:
 we have our current number and the current_sum in this step
 we decide should we take this number or no we ignore it.
 we decide does our new current_sum is greater than our global sum so we take it or we ignore it?
Lets apply an example so it can be clear for you.
Example:
nums = [2,1,3,4,1,2,1,5,4]
Remember we don't care about what is the contiguous subarray we care more about the sum of this array.
*, First of all, we define two variables
global_sum # to hold our final answer
current_sum # to hold our subarray sum

starting with making this two vars equal to our first element in our array.
global_sum = current_sum = 2

Then we start from the next number and check should we take this number or no ignore it?
current_number = 1

We check does the current number maximise our current same or reduce or even keep it the same, as we all know we need the maximum sum:
current_sum = max(current_sum, current_number + current_sum)
current_sum = max(2, 1 + 2) = max(2, 1) = 1 
Then we now we have the our new
current_sum
we need to know what will be ourglobal_sum
as well, as we said in the previous step we are searching for maximum so we need choose the max between ourcurrent_sum
value &global_sum
.global_sum = max(global_sum, current_sum)
global_sum = max(2, 1) = 1
Then we will keep doing this with the whole array until the end for the example above our answer will be
6
. I left it here for you keep doing the same on paper until the end and see what will be the result
Pseudocode:
1. define global_sum = current_sum < nums[0]
2. forloop num in nums[1:]
3. current_sum = max(current_sum, (current_sum + num))
4. global_sum = max(global_sum, current_sum)
5. return global_sum
Complexity:
Time complexity it is obvious that we do linear and that is the benefits of solving this problem using greedy so it will be O(n).
Space complexity so obvious as well we don't use any extra space instead of our two variables which are constant space, so it will be O(1).
Additional tips
1. If the given array is empty our answer will always be0
;
2. Also, if the given array only has one number which means our answer will be that number.
Please, try to figure out different solutions for the problem this is only my solution
I hope this helps any feedback will be appreciated :).
AhmedRaafat14 / Leetcodeproblems
This repository will have a lot of leetcode problems solutions
Leetcodeproblems
This repository will have a lot of problems from leetcode
 Don't expect to find expert solution am writing here my thinking thoughts of how I approached the solution.
Discussion (0)