CareerCup

Isn't this same as Kadane ?

My answer to above question

#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;

int main()
{
    int i=0;
    int j=0;
    int sum=0;
    int n = 0;
    int a[100] = {0, 0};
    int currSum=0;
    int maxSum=0;
    int outputArray[10];
    int outputArraySize = 0;
    char str[100];
    char *array[10];
    char c;
    cin.getline(str,100);

    array[i] = strtok(str," ");

    while(array[i]!=NULL)
    {
       array[++i] = strtok(NULL," ");
    }
    n = i;
    for(i=0; i< n; i++)
    {
        a[i] = atoi(array[i]);
    }
    for(i=0; i<n; i++)
    {
        sum += a[i];
    }

    if(sum<1)
    {
        return -1;
    }


    for(i=0, j=0; i<n; i++)
    {
        currSum+=a[i];
        if(currSum<0)
        {
            currSum=0;
            continue;
        }
        if(currSum>maxSum)
        {
            maxSum = currSum;
            outputArray[j++] = i;
        }
    }
    outputArraySize = j;
    for(i=0; i<outputArraySize; i++)
    {
        cout<<outputArray[i] << " ";
    }
}

def suc_run(inputA):
    best_I = -1
    best = -1
    for i in range(0,len(inputA)-1):
        if inputA[i] + inputA[i+1] > 0:
            if inputA[i] + inputA[i+1] > best:
                best = inputA[i]+inputA[i+1]
                best_I = i;
    if best == -1:
        return -1
    else:
        return best_I, best_I+1

s1 = [3, 2, -6, 2, 1]
s2 = [-2, -3, -1, 0, -6]
print suc_run(s1)
print suc_run(s2)

Its a maximum sum subsequence problem

Calculate maximum sum of consecutive items, if adding previous to current doesn't increase then restart counting.

p is auxillary array to track consecutive segment contributing to sum. maxi is index of highest sum, tracking maxi, p[maxi], p[p[maxi]] until 0 or p[i]==i would give required answer

sum[0] = a[0];
maxi = -1;
max = 0;

for(i=1; i<n; i++)
{
	sum[i] = 0;
	if( sum[i-1] + a[i] > a[i] )
		p[i] = i-1;
	else
		p[i] = i;
	
	sum[i] = sum[ p[i] ] + a[i] 
	if( max < sum[i] )
	{
		max = sum[i]
		maxi = i;
	}
}

for( i = maxi; i >=0 && i!=p[i]; i=p[i])
{
	printf(
}

Here is a simple solution..

def max_run(x):
#x = randint(-5, 8, 12)

y = x[1:]+x[:-1]

ind = where(y==max(y))[0][0]
return (ind, ind+1)

a = array([3,8,-6,9,1])

print max_run(a)}

int[] intArray = {3, 8, -6, 9, 1};
        int maxIndex = 0;
        int maxProfit = -1;

        for (int i = 0; i < intArray.length - 1; i++) {
            int currentProfit = intArray[i] + intArray[i + 1];
            if (maxProfit < currentProfit) {
                maxProfit = currentProfit;
                maxIndex = i;
            }
        }

        if (maxProfit < 0)
            System.out.println("-1");
        else
            System.out.println("<" + maxIndex + "," + (++maxIndex) + ">");