Brute Force Vs. Dynamic Program in the Maximum Subarray Problem
When I first started to code, I became interested in Ruby through solving code challenges. At first, it was quite difficult to solve even the simplest of problems due to my lack of experience. But as I solved more problems, the solutions came to me more quickly. I was solving all the basic problems using the method known as brute force.
What is Brute Force?
Brute force is a general problem-solving technique which basically checks all possible solutions. I solved most of my early coding challenges using this technique because this was the only way I knew how. As the challenges started to get harder, more advanced and strategic strategies became required of me.
Maximum Subarray Problem
Given an array of numbers, find the largest consecutive subarray sum.numbers = [2, -9, 5, -4, 10]e.g of subarray: [2, -9, 5].reduce(:+) = -2
I chose to solve this problem because it was a very popular coding challenge used by companies such as Amazon, Microsoft, Linkedin and Samsung. When given an array of values, I started by using a brute force solution. I created two variables and incremented each one with every iteration. I checked every possible subarray inside numbers and stored the value if it was larger than my current value.
Brute Force Solution
def array_max_consecutive_sum(numbers)
largest_sum = 0
current_sum = 0
index_one = 0
while index_one < numbers.count index_two = index_one
while index_two < numbers.count current_sum = numbers[index_one..index_two].reduce(:+) if current_sum > largest_sum
largest_sum = current_sum
end index_two += 1
end index_one += 1
end largest_sum
end#Code checks every subarray with the indexes
What its checking:[2] #2
[2, -9] #-7
[2, -9, 5] #-2
[2, -9, 5, -4] #-6
[2, -9, 5, -4, 10] #4
[-9] #-9
[-9, 5] #-4
[-9, 5, -4] #-8
[-9, 5, -4, 10] #2
[5] #5
[5, -4] #1
[5, -4, 10] #11----- largest_sum will save and return this value
[-4] #-4
[-4, 10] #6
[10] #10
This is a simple and functional solution, but there is one problem. It is inefficient. This method helped me pass a few tests, but as the number array grows, the amount of time it takes to find the largest sum does as well. Eventually when the numbers array gets too large, the code will timeout. I decided to find a new way to solve this problem.
What is Dyanamic Programing ?
Dynamic Programming is the method of using prior knowledge gathered from the problem in order to solve a more complex one. In programming, this usually means solving each sub-problem once and then storing the data in a collection. When more difficult problems arise, this collection could be called upon and used to help find the solution.
Kadane’s Theorem in Maximum Subarray Problem
def array_max_consecutive_sum(numbers)
current_max = current = 0 numbers.each do |num|
current = [num, (current + num)].max
current_max = [current_max, current].max
end current_max
endmax values: 2 --> -7 --> 5 --> 1 --> 11
current_max values: 2 --> 2 --> 5 --> 5 --> 11#slice changes values when max becomes larger than the slice.
Difference Between Brute Force and Dynamic Programming
The biggest difference between these two methods is efficiency. The Brute force solution iterates over the array many times in order to get every possible solution. The Dynamic programming solution only iterates through the array once.
Using this problem as an example, if the amount of numbers in the array was 100,000, the brute force solution would eventually time out because the amount of iterations it would have to do would be too many. The dynamic solution would still work because it only needs to go through the array one time.
In conclusion, this problem helped me see what was possible with code. Just because something works does not mean its the best way to solve a problem. Thinking outside the box can help with creating more efficient and elegant solutions to future problems. Thanks for reading!
