The difference between two sequences of the same length {a1, a2, a3, ..., an} and {b1, b2, b3, ..., bn} can be defined as the sum of the absolute differences between their respective elements: diff(a, b) = { |a1 b1|, |a2 b2|, |a3 b3|, ..., |an bn| } For the given sequences a and b (not necessarily having the same lengths), find the subsequence a or a and subsequence b of b such that diff(a, b) is minimal. Return the difference. Example: A= {1, 2, 6}, b = {0, 1, 3, 4, 5}, the output should be smallestDifference(a, b) = 2, where the bestsubsequence will be b = {1, 3, 5}

1.Implement a recursive version of the smallestDifference function in the smallestDifference_recursive_utility function. There is no time restriction on this solution

2.Implement an amortized version of the smallestDifference function in the smallestDifference_amortized_utility function. The maximum timefor this function to identify the solution is 500ms (regardless of input size).

3.Implement a loop-based version of the smallestDifference function in the smallestDifference_optimized function. The maximum time for this function to identify the solution is 500ms (regardless of input size).

4.The length of a will be in the range [3, 1000].

5.The length of b will be in the range [a.length, 1000]

6.The values in each array will be in the range [-1000, 1000]

#include #include #include "smallest_difference.h"

int smallestDifference_recursive_utility(const std::vector& a, const std::vector& b, int aPos, int bPos) {

}

int smallestDifference_recursive(const std::vector& a, const std::vector& b) { return smallestDifference_recursive_utility(a, b, a.size(), b.size()); }

int smallestDifference_amortized_utility(const std::vector& a, const std::vector& b, int aPos, int bPos, std::vector >& results) { }

int smallestDifference_amortized(const std::vector& a, const std::vector& b) { std::vector > results(a.size(), std::vector(b.size(), -1)); return smallestDifference_amortized_utility(a, b, a.size(), b.size(), results); }

int smallestDifference_optimized(const std::vector& a, const std::vector& b) { }