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.


  • TheV
    I 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.😔
  • silverscorpion
    If there is no restriction on the size of the sub-array, then I think the algorithm is very straight-forward, 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 sub-array, then an easy way to find the maximum sum of all sub-arrays 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
  • silverscorpion
    Ok, i made a very bad mistake..

    The problem is about sub-arrays, and hence, order of the elements matters.
    So, sorting or heap is not the solution.

    Will return to this problem later.. 😀
  • simplycoder
    Refer to the C-programing 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 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...