Please help with finding the largest consecutive sum of a circular linked list of integers

[Bubiche]

So I have a circular linked list with each Node given by:

struct Node
{
	int val;
	Node* Next;
};

I'm asked to write a program to find largest the sum of consecutive nodes in the list.
Example Input/Output:

Input: 5 9 -99 2
Output: 16

What I'm thinking about is using the Kadane's algorithm given here (changed it a bit to apply for linked list): http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm

First I check whether all nodes are negative numbers. If so, the answer would be the biggest negative node.

If not all nodes are negative numbers then I'll use Kadane's algorithm to find the maximum sum of nodes without "going around" the circle. In the example it would be 5+9=14. I call this result number A.
Then, I multiply each node by -1, use Kadane's algorithm again to get number B(this will get B=99 in the example). After that I'll take number C = (Sum of all nodes) + B (C=16 in the example).
The answer would now be max(A,C).

Please help and tell me if my solution is correct. Is there any better algorithms out there? (I'm not asking for the code, just the algorithm) Can I extend this problem to get the chosen nodes for the largest sum too?
Thank you for your time and patience.

[keskiverto]

What if your input is

5 9 -89 7 -99 2

On the other hand, what if you would expand the list almost twice: [0..n-1, 0..n-2]
That will contain each n-long subsequence (but then some).

[Bubiche]

Thank you for your answer keskiverto

For input

5 9 -89 7 -99 2

The answer would be 16 right?
Then with the way I posted, number A would be 14 (5+9), number B would be 181 (89-7+99), number C would be 16 (81 + (5+9-89+7-99+2). So the result is max(14,16)=16. As far as I understand, Kadane's algorithm can find the largest sum subset of numbers if the list is not all negative.(I've tested quite a few times)

Is there a way that I can make use of fact that a circular linked list have the last node's Next pointer points to the first node? Expanding the list would make it feels just like I'm working with a singly linked list or a array

[keskiverto]

So, essentially, the circle has exactly two segments: the maximal subsequence and the minimal subsequence?

The wikipedia C++ example for Kedane records "the beginning and ending indices of the maximum subarray". If you have recorded the indices for both minimal and maximal subarrays, then you can deduce which is entirely within the range and whether the other is too, or overlaps to the next round.

[Bubiche]

Actually what I was trying is multiply each element of the circle by -1 then find the maximum subarray of the new circle, which I think would be the minimum subarray of the original circle, so the circle doesn't really have 2 segments or anything.
I'm asking if my thoughts are correct and is there a better way especially a way that I can make use of the nature of the circle that we can move from the last element to the first one easily unlike with a normal linked list

[keskiverto]

I think that the logic is a bit off here, but the aim is to iterate elements in the cycle until you meet the first node again, but with X you can initially disable that end condition (i.e. do more than one cycle).

Node * curr = head;
int count = 0;
do {
  // code
  if ( head == curr ) ++count;
  curr = curr->Next;
} while ( count < X || curr != head );

Input was: 5 9 -89 7 -99 2
B was: -89 7 -99
C was: 2 5 9
Is there any scenario, where B and C together do not contain all elements of Input? val==0

A contains elements 0-1. B contains elements 2-4. Neither has element 5. 5 cannot belong to B. If it would, then B would already be 2-5. ==> make C := A + 5.