We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I finally had success with a recursive solution in C++11. It does do some repetitive work and could probably be made more efficient.
Basically, it picks a cell in the middle of the range of length n; n/2 == k.
* First it assumes that arr[k] isn't part of the solution, and it solves recursively for the ranges on either side of that cell [0, k-1] and [k+1,n] and returns the sum.
* If arr[k] is positive, then it might be part of the solution, so it also solves recursively for [0, k-2], [k+2, n], adding arr[k] to the new sum. If that sum is higher than the previous sum, then it returns that valueinstead.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Max Array Sum
You are viewing a single comment's thread. Return to all comments →
I finally had success with a recursive solution in C++11. It does do some repetitive work and could probably be made more efficient.
Basically, it picks a cell in the middle of the range of length n; n/2 == k. * First it assumes that arr[k] isn't part of the solution, and it solves recursively for the ranges on either side of that cell [0, k-1] and [k+1,n] and returns the sum. * If arr[k] is positive, then it might be part of the solution, so it also solves recursively for [0, k-2], [k+2, n], adding arr[k] to the new sum. If that sum is higher than the previous sum, then it returns that valueinstead.