Programming Challenge : Write An Efficient Code!
In an array of integers,find the subarray that has the greatest value when all of its elements are summed together.
Note that because some elements of the array may be negative, the problem is not solved by simply picking the start and end elements of the array to be the subarrray, and summing the entire array.
For example, given the array
{1, 2, 5, 4, 3, 2}
The maximum sum of a subarray is 4. It is possible for the subarray to be zero elements in length (if every element of the array were negative).
Before you write the code, take some time to think of the most efficient solution possible; it may surprise you. The major goal of this challenge is to test your algorithmic skills rather than merely your ability to write code quickly.
Note that because some elements of the array may be negative, the problem is not solved by simply picking the start and end elements of the array to be the subarrray, and summing the entire array.
For example, given the array
{1, 2, 5, 4, 3, 2}
The maximum sum of a subarray is 4. It is possible for the subarray to be zero elements in length (if every element of the array were negative).
Before you write the code, take some time to think of the most efficient solution possible; it may surprise you. The major goal of this challenge is to test your algorithmic skills rather than merely your ability to write code quickly.
Replies

TheVI did got your question..! Can you please explain me a little...What will be the size of the subarray? if I will consider {1,2,4} then the maximum will be 7 or if we consider {1,2,4,2} the maximum will be 9. Or I consider all the subset of the array i.e. 2^n arrays.ðŸ˜”

silverscorpionIf there is no restriction on the size of the subarray, then I think the algorithm is very straightforward, and is something like this:
Check if there are negative elements in the array. If there are no negative elements : return the sum of the entire array Else : return the sum of the array with the negative elements removed
ie., if there are no negative elements, then the sum of the entire array will obviously be the biggest. If there are some negative elements, then simply remove them and the sum of the remaining elements will be the largest. We can probably remove the zeroes as well, but it won't make a difference.
If there is a restriction on the size of the subarray, then an easy way to find the maximum sum of all subarrays of a given size is,
(assuming the array is sorted in ascending order)
Sort the array return the sum of the last n elements
Of course, there are many sorting algorithms and the most efficient one to use will depend on many properties of the array to be sorted.
Or, you can also build a heap from the array, and then get the first n maximum elements from the heap.
Finally, in both the above methods, it will be good to have one more condition, like:
if all the elements in the array are negative or zero : return 0

silverscorpionOops...
Ok, i made a very bad mistake..
The problem is about subarrays, and hence, order of the elements matters.
So, sorting or heap is not the solution.
Will return to this problem later.. ðŸ˜€ 
simplycoderRefer to the Cprograming tutorial where in I have solved this question.
The solution I have given is not an efficient one, it can be still done better.
I don't want to spoil it by giving the answer, however I might just hint you guys that it requires lesser time than n^2 and this can be obtained by some thing called as divide and conquer. I would post my answer soon if no one is getting it.
You are reading an archived discussion.
Related Posts
Write a function that takes a string and returns the ROT13 version of the string; you may assume that the character set is ascii. What is the meaning of â€œCebtenzzvat...
In a typical HR interview, you might be asked to differentiate between Confidence and Overconfidence. Can you list a few points?
I need your help..i am doing BE(ece),i finished my first year with 9.2 gpa..then entered into our department..in my mind there is only one thing that came into my mind...
This comes as a tricky question for many.
How would you answer if the interviewer asks you, "Aren't you over qualified for this job profile?"
All the CS & IT Students have to study 'Turing Machine' under computation theory.
Quoting from wikipedia:
A Turing machine is a device that manipulates symbols on a strip of...