Programming Challenge : Write An Efficient Code!

Ankita
Member • Dec 13, 2011

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.

Replies

Howdy guest!

Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.

Replies

TheV

Member • Dec 13, 2011

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

Are you sure? This action cannot be undone.
Cancel
silverscorpion

Member • Dec 14, 2011
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
```
Are you sure? This action cannot be undone.
Cancel
silverscorpion

Member • Dec 14, 2011

Oops...
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.. 😀

Are you sure? This action cannot be undone.
Cancel
simplycoder

Member • Dec 15, 2011

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.

Are you sure? This action cannot be undone.
Cancel