Skip to content

Instantly share code, notes, and snippets.

@rishiip

rishiip/find-max-subarray

Created December 21, 2015 17:50
Show Gist options
  • Save rishiip/15b7f8ffd409e2383934 to your computer and use it in GitHub Desktop.
Save rishiip/15b7f8ffd409e2383934 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
find-max-subarray
def get_array_max(one_dim_array)
one_dim_array.inject([0, 0]) do |(max_so_far, max_up_to_here), x|
new_max_up_to_here = [max_up_to_here + x, 0].max
new_max_so_far = [max_so_far, new_max_up_to_here].max
[new_max_so_far, new_max_up_to_here]
end.first
end
sample = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
p get_array_max(sample)
@kcore
Copy link

kcore commented Dec 22, 2015

this just returns the sum. Can i get the sub_array as well?

@rishiip
Copy link
Author

rishiip commented Dec 22, 2015

@kcore You can get sub_array with two elements who is having max sum by just replacing 6th line (https://gist.github.com/rishiip/15b7f8ffd409e2383934#file-find-max-subarray-L6) with writing just end.

@kcore
Copy link

kcore commented Dec 22, 2015

[6, 5] is the answer. what is 5 supposed to mean? the index of the input array? shouldn't we have 2 indexes - start and end to define the sub_array?

@rishiip
Copy link
Author

rishiip commented Dec 23, 2015

@kcore I believe that 5 here is the second highest element not the index of the input array.

@kcore
Copy link

kcore commented Dec 23, 2015

wait.. may i ask what was the program supposed to return here?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment