Maximum Subsequence Sum is one of the classic problems found in the Data Structures & Algorithms books.
Given a one dimensional array of integers, the task is to find a contiguous subarray with the largest sum.
-1 -3 5 -2 -1 3 1 -2
For the above array, the MaxSubsequenceSum is 6 which is obtained by starting from the 3rd element which is 5 and up to the last but one element which is 1.
5 + (-2) + (-1) + 3 + 1 = 6
This exercise also is not that difficult. Just to spice up the exercise please implement the naive or
brute force solution also. Divide and Conquer strategy also can be used and you can optionally implement that solution also.
As usual, please pay attention to the documentation, inline comments, and checking of illegal arguments.
The Divide & Conquer strategy which makes use of Recursion is not straight forward and not easy to understand. Normally recursive solutions are simple, elegant and easy to understand. As this one is not, I make the recursive implementation optional.
I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.
You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.
Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.
Here is the link to my solution.
Given a one dimensional array of integers, the task is to find a contiguous subarray with the largest sum.
-1 -3 5 -2 -1 3 1 -2
For the above array, the MaxSubsequenceSum is 6 which is obtained by starting from the 3rd element which is 5 and up to the last but one element which is 1.
5 + (-2) + (-1) + 3 + 1 = 6
This exercise also is not that difficult. Just to spice up the exercise please implement the naive or
brute force solution also. Divide and Conquer strategy also can be used and you can optionally implement that solution also.
As usual, please pay attention to the documentation, inline comments, and checking of illegal arguments.
MaxSubsequenceSum Implement the class MaxSubsequenceSum with the following public methods. public int findMaxSubsequenceSum(int[] anInput); public int findMaxSubsequenceSumUsingBruteForce(int[] anInput); public int findMaxSubsequenceSumUsingDivideAndConquer(int[] anInput);
The Divide & Conquer strategy which makes use of Recursion is not straight forward and not easy to understand. Normally recursive solutions are simple, elegant and easy to understand. As this one is not, I make the recursive implementation optional.
I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.
You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.
Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.
Here is the link to my solution.
Post a Comment
Post a Comment