Programming Challenge : Write An Efficient Code!

Replies

• 

  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

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

  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.