CareerCup

<pre lang="c++" line="1" title="CodeMonkey71091" class="run-this">/* Is implemented as an array but no random accesses and the conversion to linked list is trivial */
#include<stdlib.h>
#include<stdio.h>
#define SIZE 10
bool verify(int start, int array[])
{
int sum = 0;
for(int i=start, j=0;j<SIZE;j++, i = (i+1)%SIZE)
{
sum += array[i];
printf("%d %d\n", sum, array[i]);
}
}
void FindPositiveSubArray(int array[])
{
int sum = 0;
int current = 0;
while(array[current]<=0 && current<SIZE)
current++;
if(current==SIZE)
printf("-1\n");
sum = array[current];
int start = current, diff = 1;
current++;
while(start<SIZE)
{
sum += array[current];
while(sum<=0 && start<SIZE && start<current)
{
sum-=array[start];
diff--;
start++;
}
if(start == current)
{
while(array[current]<=0)
{
current = current+1;
if(current == SIZE)
{
printf("-1\n");
return;
}
current = current%SIZE;
}
start = current;
sum = array[current];
}
current++;
diff++;
if(diff == SIZE)
break;

}
if(start!=SIZE)
printf("%d\n", start);
else{
printf("-1\n");
}
}
int main()
{
int i;
int array[SIZE] = {2, -3, 4, -5, 6, -7, 10, -6, 7, -7}, pows[2] = {1, -1};
int sign = pows[rand()%2];
/*for(i=0;i<SIZE;i++)
{
array[i] = sign * rand()%1000;
printf("%d %d\n", i, array[i]);
sign*=-1;
}*/
FindPositiveSubArray(array);
}</pre><pre title="CodeMonkey71091" input="yes">
</pre>

If any such node is sufficient, then the node with the largest positive value should be the one (if any such node exists).

The sum of the complete linked list shall be the same. No matter in which order u add. If we start n finish at the same node then is it not like adding all the positive and negative numbers which shall always give the same answer??

I agree with xyz, the sum remains the same no matter where you start and sum up all the node values. Can we have some clarification of the question.

i think we need to exclude the current node data.. tht will differentiate the answer..

The list has alternate +ve & -ve numbers. So we always has to start with a +ve no. Jump 2 steps while checking each time you start checking for the position.

1> find the sum of all the elements in the list.
2> for i=start;i<=size;i=i->Next
3> if ((sum-i) >= 0)
4> return i

Complexity O(n)

Such node does not exist necessarily. we are anyways adding all the nodes in list since its circular list, so if sum of all nodes is not positive, there is no such node in list which gives +ve sum