Write a function called bestSimilarity that finds the best similarity score between all subsequences of an input tune and the target tune. The input tune will always be as long as or longer than the target tune. In other words, this function will find the best possible similarity score that a tune could have. See the worked example below for a deeper explanation of how this function should work.

Function Specifications:

The function name: bestSimilarity

Parameters (Your function should accept these parameters IN THIS ORDER):

string input_tune: The input tune to be checked against the target (length greater than or equal to the target tune)

string target_tune: The target tune

Return Value: The best possible similarity score (double)

The length of input_tune should be greater than or equal to the length of target_tune. If input_tune is shorter than target_tune, your function should return 0.

The function should not print anything.

This function should make use of the tuneSimilarity function created in question 4.

You may assume that the input to bestSimilarity will always be valid SPN, i.e. you do not have to account for arbitrary strings.

A worked example:

Input tune	Target tune	Similarity Calculation	Similarity Score
A0E2D4E5C1F0	D4E5C0	1/3 + 0 - 2	-1.66667
A0E2D4E5C1F0	D4E5C0	0/3 + 0 - 3	-3
A0E2D4E5C1F0	D4E5C0	3/3 + 2 - 0	3
A0E2D4E5C1F0	D4E5C0	0/3 + 0 - 2	-2

Thus, the highest possible similarity score out of every subsequence of our target tune is 3.00, so our function would return 3.00.

--- Examples ---

Sample function call	Expected return value
bestSimilarity("E4D5B7G2E2", "D6G5G2")	0.666667
bestSimilarity("F1E2C2D1A7B8D3", "F2A7C3")	-0.333333
bestSimilarity("A2G7", "E9D2C4F1")	0

An example test case for the first sample function call would be: assert(doubles_equal(bestSimilarity("E4D5B7G2E2", "D6G5G2"), 0.666667));

Your file should be named bestSimilarity.cpp and should also include your tuneSimilarity function along with a main function that tests your new bestSimilarity function. Once you have finished developing your solution in VSCode you should head over to the CodeRunner on Canvas and paste only your bestSimilarity function into the answer box for question 5. You do not need to paste your main function into Coderunner. A main function has already been provided for you. You will need to include your main, bestSimilarity and any other helper functions in the bestSimilarity.cpp file that you submit to Canvas.