Write a program that solves Exercise 2.19. You need to modify the programs for each of the 4 algorithms for the maximum-subsequence-sum problem so that the program not only returns the maximum sums of subsequences of the given integer array but also returns/outputs the actual subsequence where the sum of integers is maximum. Run each algorithm on three randomly generated integer arrays of sizes N=1,000, 10,000, and 100,000, measure the running times, and determine if they are consistent with the theoretical analysis results of those algorithms given.

Exercise 2.19: The maximum contiguous subsequence sum algorithms in the text do not give any indication of the actual sequence. Modify them so that they return in a single object the value of the maximum subsequence and the indices of the actual sequence.