Samuel Arwood

Greenhorn

Posts: 6

posted 5 years ago

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.

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

posted 5 years ago

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.

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

posted 5 years ago

You cannot return two values from a method. You would have to create an object to encapsulate those two values. A two‑element

If you use a method with

`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

posted 5 years ago

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?

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?

posted 5 years ago

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

2. Define those variables (

HIH

Winston

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Campbell Ritchie

Marshal

Posts: 56518

172

posted 5 years ago

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 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

Articles by Winston can be found here

Don't get me started about those stupid light bulbs. |