This is my first post here for help, so if I left out any information that would be needed just let me know. Thanks everyone.
You can never see an algorithm on screen. You need to write it on paper. Write down on paper how you would do it by hand, and then convert it into code. If this is a programming exercise, rather than a maths exercise, you should have been given the algorithm. Otherwise you can probably find it in a book, Google or Wikipedia.
If you use a method with void return type, you would have to record the two indices somewhere. If they are fields of your class, then you would require an instance of the class to store those fields. If it is an instance, then your method must not be static.
I don't need to "return" two values, per se. The object Algorithm holds all of the values that need to be printed for each of the different algorithms we are testing. It has values for the time the algorithm took, the max sum (to make sure it actually worked), the starting and ending indices, etc. and it is printed after the recursive functions complete.
I just don't know how to really go about keeping track of the starting and ending points. I can keep track of the endpoints if and only if the max sum is only one array index. But once the max value is the max left and max right, or is more than one index, I don't know how to go back and use the previous levels bounds for that left and right max. Does that make sense?
Samuel Arwood wrote:I just don't know how to really go about keeping track of the starting and ending points. I can keep track of the endpoints if and only if the max sum is only one array index. But once the max value is the max left and max right, or is more than one index, I don't know how to go back and use the previous levels bounds for that left and right max. Does that make sense?
Yup, and recursion is quite tricky that way; which is why even experienced programmers generally only use when it really benefits.
As Campbell said, there are two ways:
1. Pass the values that you'll need back to the preceding level; maybe, as he suggests, by returning an int instead of just a single int. An alternative might be to create a Result class into which you can poke your max sum and the boundaries that generated it, and have your method return that.
2. Define those variables (maxSum, maxSumStart and maxSumEnd) outside the method altogether. Slightly more coupled, but sometimes the easiest when you're writing recursive functions.
Campbell Ritchie wrote:That algorithm looks more complicated than what I found when I looked in Wikipedia earlier today.
If you mean Kadane's, then yes. However, when I searched I found some notes for an 'analysis of algorithms' course, which compared this method with Kaldane's and two others (including a brute force method). Maybe that's what they're doing.
BTW, that Kadane solution really is a thing of beauty...and deceptively simple.