• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to return indices of max sum sub-sequence?  RSS feed

 
Samuel Arwood
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That algorithm looks more complicated than what I found when I looked in Wikipedia earlier today.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can’t do a Homer Simpson auauauauaaurghhhhhhhhhh! but Kadane merits it!
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!