programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# How to return indices of max sum sub-sequence?

Greenhorn
Posts: 6
In this case I have recursive code to find the max sum subsequence in an array. I need help keeping track and finding the final subsequence indices in the array. This code works to find the max sum, but how would I modify it to find at what indices this sum is between?

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.

Marshal
Posts: 58454
178
Welcome to the Ranch

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.

Campbell Ritchie
Marshal
Posts: 58454
178
You cannot return two values from a method. You would have to create an object to encapsulate those two values. A two‑element int[] array is a possible type.
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.

Samuel Arwood
Greenhorn
Posts: 6
Thanks for the reply. Oh if you could only see the mess of paper with my attempt to this exercise. This is an exercise for an algorithm analysis class i'm taking and the coding part is supposed to be easy, but I guess I haven't grasped it as well as I thought.

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?

Bartender
Posts: 10575
66

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.

HIH

Winston

Campbell Ritchie
Marshal
Posts: 58454
178
That algorithm looks more complicated than what I found when I looked in Wikipedia earlier today.

Winston Gutkowski
Bartender
Posts: 10575
66

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.

Winston

Campbell Ritchie
Marshal
Posts: 58454
178
I can’t do a Homer Simpson auauauauaaurghhhhhhhhhh! but Kadane merits it!

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.