CareerCup

Kadane algorithm in Java

private static void kadaneAlgo(int[] input){
        int max_curr=input[0];
        int curr_start=0;
        int curr_end=0;
        int max_ref=Integer.MIN_VALUE;
        int max_start=0;
        int max_end=0;
        for(int i=0;i<input.length;i++){
            if(input[i] > max_curr+input[i]){
                max_curr=input[i];
                curr_start=i;
                curr_end=i;
            }else{
                max_curr+=input[i];
                curr_end=i;
            }
            if(max_curr>max_ref){
                max_ref=max_curr;
                max_start=curr_start;
                max_end=curr_end;
            }
        }
        System.out.println("Max sum of subarray --> "+max_ref+" with index start "+max_start+" index end "+max_end);
    }

Kadane algorithm , taking into account negative cases

public static ArrayList findConsecutiveMaxSum(int[] nums){

        if(nums.length<1) return null;

        ArrayList<Integer> res = new ArrayList<>();

        int maxSofar, currMax,startIndx =0,endIndx =0;

        maxSofar = currMax = nums[0];

        for (int i = 1 ; i< nums.length ;i++){

            if(currMax + nums[i] < nums[i]) startIndx = i;

            currMax = Math.max(nums[i],currMax+nums[i]);

            if(maxSofar<currMax) endIndx = i;

            maxSofar = Math.max(maxSofar,currMax);

        }

        for (int i = startIndx ; i<=endIndx ;i++) res.add(nums[i]);
        
    if(endIndx<startIndx) res.add(nums[endIndx]);
       
        return res;
    }

The below code will give you max Sum in O(N).
We just have to get the startIndex and endIndex(when you make tempSum 0) and get the values in-between them.

public static int maxSum(int[] numbers)
	{
		/*
		 *  Handle Edge cases
		 *  1. is input Array is NULL
		 *  2. If input Array has only one element
		 */
		if(numbers == null)
		{
			return -1;
		}
		int maxSum = 0;
		int tempSum = 0;
		// int numbers[] = { 1 , 3 , -5 , 3 , 2 , 1 , -3 , 4 , 2 , -12 , 2 , 3}	
		// Iterating through the array 0...N
		for(int i=0; i< numbers.length; i++)
		{
			// Adding it to temp Sum
			tempSum = tempSum + numbers[i];
			if(maxSum < tempSum)
			{
				maxSum = tempSum;
			}
			// If temp Sum is less than 0, making it to Zero.
			// Ex: 1 + 3 + -5 = -1. In this case, making tempSum to Zero, so that -1 doesnt affect the sum of the next sequence
			else if(tempSum < 0)
			{
					tempSum = 0;
			}		
		}
		return maxSum;
	}

Could you explain more about interview - is it phone call or site.

modified Kadane.
c#

private static int[] Kadane( int[] arr ) {

    var coords = new int[2] { 0, 0 };
    int maxByNow = arr[ 0 ], greatest = arr[ 0 ];

    for (int i = 1; i < arr.Length; i++) {
        if ( maxByNow < 0 ) { coords[ 0 ] = i; }
        maxByNow = Math.Max( arr[ i ], maxByNow + arr[ i ] );
        var tmp = Math.Max( greatest, maxByNow );
        if ( tmp > greatest ) { coords[ 1 ] = i; }
        greatest = tmp;
    }
    int[] res = new int[ coords[ 1 ] > coords[ 0 ] ? coords[ 1 ] - coords[ 0 ] + 1 : 1 ];
    res[ 0 ] = arr[ coords[ 1 ] ];
    for ( int i = coords[ 0 ]; i <= coords[ 1 ]; i++ ) {
        res[ i - coords[ 0 ] ] = arr[ i ];
    }
    return res;
}

#include<stdio.h>
int main(){
int n=0,i=0;
int max_end=0;
int max_far=0;
scanf("%d",&n);
int array[n];
while(i<n){
scanf("%d",&array[i]);
i++;
}
for(i=0;i<n;i++){
max_end=max_end+array[i];
if(max_end<0){
max_end=0;
}
if(max_far<max_end){
max_far=max_end;
}
}
printf("%d",max_far);
}

O(N) solution in Python
returns a list of consecutive numbers with the biggest sum

def findConsecutiveIntegerBiggestSum(l):
    
    if type(l) != list:
        raise Exception('input is not a list')
    if len(l) == 0:
        raise Exception('list is empty')
    
    accum_li = [0] * len(l)
    accum = 0
    ct_pos = 0
    for i, v in enumerate(l):
        accum += v
        accum_li[i] = accum
        if v > 0:
            ct_pos += 1

    if ct_pos < 2:
        return [max(l)]
    
    best_sum = accum_li[-1]
    best_low = 0
    best_high = len(l) - 1
    
    curr_low = 0
    curr_high = len(l) - 1
    
    while(curr_high - curr_low > 1):
        
        curr_sum = accum_li[curr_high] - accum_li[curr_low]

        if curr_sum > best_sum:            
            best_sum = curr_sum
            best_low = curr_low + 1
            best_high = curr_high
            
        if l[curr_low] > l[curr_high]:
            curr_high -= 1
        else:
            curr_low += 1
            
    return l[best_low : best_high + 1]

- Python
- O(N)
- needs two pass over entire list
- returns a list containing consecutive numbers which give the max sum

def findConsecutiveMaxSum(l):
    
    if type(l) != list:
        raise Exception('input is not a list')
    if len(l) == 0:
        raise Exception('list is empty')
    
    accum_li = [0] * len(l)
    accum = 0
    ct_pos = 0
	
    #first pass: integrate over list
    for i, v in enumerate(l):
        accum += v
        accum_li[i] = accum
        if v > 0:
            ct_pos += 1

    if ct_pos < 2:
        return [max(l)]
    
    best_sum = accum_li[-1]
    best_low = 0
    best_high = len(l) - 1
    
    curr_low = 0
    curr_high = len(l) - 1
    
    #second pass: try to improve sum
    while(curr_high - curr_low > 1):
        
        curr_sum = accum_li[curr_high] - accum_li[curr_low]

        if curr_sum > best_sum:            
            best_sum = curr_sum
            best_low = curr_low + 1
            best_high = curr_high
            
        if l[curr_low] > l[curr_high]:
            curr_high -= 1
        else:
            curr_low += 1
            
    return l[best_low : best_high + 1]

I'm preparing to apply for tech companies next months and wanted to ask you guys. How on earth am I supposed to know there is an algorithm called "Kadane algorithm" would solve this problem? Do you learn that at school? (I'm from a different country)

My thinking of tech interviews was that it measures how someone could find a solution for a given problem in a short period of time, not memorize unknown algorithms and write them down at the time of interview. So frustrating.

This code returns a list of the elements that gives the max sum, the code uses dynamic programming

public List<int> FindMaxSum(int[] values)
{
    int sum = values[0];
    int index = 0;
    int maxSum = values[0];
    int maxIndex = 0;
    int minIndex = 0;

    for (int i = 1; i < values.Length; i++)
    {
        if (sum + values[i] > values[i])
        {
            sum += values[i];
        }
        else
        {
            sum = values[i];
            index = i;
        }

        if (sum > maxSum)
        {
            maxSum = sum;
            maxIndex = i;
            minIndex = index;
        }
    }

    var result = new List<int>();
    for (int i = minIndex; i <= maxIndex; i++)
        result.Add(values[i]);

    return result;
}

Prints the largest sum, and the start/end indices (indices begin from 0). Change array vars and length if needed.

#include <stdio.h>

main()
{
    int nums[100] = {-2,1,-3,4,-1,2,1,-5,4}, length = 9, i = 0, j = 0;
    int largestSum = 0, largestSumBegin = 0, largestSumEnd = 0; 
    int tempSum = 0, tempSumBegin = 0;

    for (i = 0; i < length; i++) {
         if (i == 0) {
             largestSum = tempSum = nums[i];
         }
         tempSum += nums[i];
         if (tempSum > largestSum) {
             largestSum = tempSum;
             largestSumBegin = tempSumBegin;
             largestSumEnd = i;
         }
         if (tempSum < 0) {
             tempSum = 0;
             tempSumBegin = i+1;
         }
    }

    printf("\nlargest sum = %d, start idx = %d, end idx = %d", largestSum, largestSumBegin, largestSumEnd);

}

#include <stdio.h>

main()
{
    int nums[100] = {-2,1,-3,4,-1,2,1,-5,4}, length = 9, i = 0, j = 0;
    int largestSum = 0, largestSumBegin = 0, largestSumEnd = 0; 
    int tempSum = 0, tempSumBegin = 0, tempSumEnd = 0;

    for (i = 0; i < length; i++) {
         if (i == 0) {
             largestSum = tempSum = nums[i];
         }
         tempSum += nums[i];
         if (tempSum > largestSum) {
             largestSum = tempSum;
             largestSumBegin = tempSumBegin;
             largestSumEnd = i;
         }
         if (tempSum < 0) {
             tempSum = 0;
             tempSumBegin = i+1;
         }
    }

    printf("\nlargest sum = %d, start idx = %d, end idx = %d", largestSum, largestSumBegin, largestSumEnd);

}

void max_sum_cons(const int* arr, const int n)
{

    int starting_pt[n];
    int sums[n];
    
    sums[0] = arr[0];
    starting_pt[0] = 0;
    
    int max_sum = sums[0];
    int max_loc = 0;
    
    for(int i = 1; i < n; ++i)
    {
        if(sums[i-1] > 0)
        {
            sums[i] = sums[i-1] + arr[i];
            starting_pt[i] = starting_pt[i-1];
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
        else
        {
            sums[i] = arr[i];
            starting_pt[i] = i;
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
    }
    
    for(int i = starting_pt[max_loc]; i <= max_loc; ++i)
        std::cout << arr[i] << " ";
        
    std::cout << std::endl;
}

void max_sum_cons(const int* arr, const int n)
{

    int starting_pt[n];
    int sums[n];
    
    sums[0] = arr[0];
    starting_pt[0] = 0;
    
    int max_sum = sums[0];
    int max_loc = 0;
    
    for(int i = 1; i < n; ++i)
    {
        if(sums[i-1] > 0)
        {
            sums[i] = sums[i-1] + arr[i];
            starting_pt[i] = starting_pt[i-1];
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
        else
        {
            sums[i] = arr[i];
            starting_pt[i] = i;
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
    }
    
    for(int i = starting_pt[max_loc]; i <= max_loc; ++i)
        std::cout << arr[i] << " ";
        
    std::cout << std::endl;
}

public static int findHighestSum(int[] arr){
        int temp = 0;
        int max = Integer.MIN_VALUE;
        for(int num : arr){
            if(max < 0){
                if(num>max){
                    max = num;
                    temp = max;
                }else{
                    temp+=num;
                }
            }else{
                if(num+temp>max){
                    max = num+temp;
                    temp = max;
                }else{
                    temp+=num;
                }
            }
        }
        return max;
    }

My version in Python, O(n):

from sys import maxint

def max_subarray(A):
    max_ending_here = max_so_far = 0
    index_low = index_high = 0
    negative_case = -maxint

    for x in A:
    	if max_ending_here + x > 0:
    		max_ending_here += x
    	else:
    		max_ending_here = 0
    		index_low = A.index(x) + 1

    	if max_ending_here > max_so_far:
    		max_so_far = max_ending_here
    		index_high = A.index(x)

    	if x > negative_case:
    		negative_case = x

    if sum(A[index_low:index_high]) == 0:
    	return negative_case
    return max_so_far,index_low,index_high,A[index_low:index_high + 1]

A = [-2,-7,-6,-4,-1,-5,-8,-1,-7]
print max_subarray(A)

My version in Python, O(n)

from sys import maxint

def max_subarray(A):
    max_ending_here = max_so_far = 0
    index_low = index_high = 0
    negative_case = -maxint

    for x in A:
    	if max_ending_here + x > 0:
    		max_ending_here += x
    	else:
    		max_ending_here = 0
    		index_low = A.index(x) + 1

    	if max_ending_here > max_so_far:
    		max_so_far = max_ending_here
    		index_high = A.index(x)

    	if x > negative_case:
    		negative_case = x

    if sum(A[index_low:index_high]) == 0:
    	return negative_case
    return max_so_far,index_low,index_high,A[index_low:index_high + 1]

A = [-2,-7,-6,-4,-1,-5,-8,-1,-7]
print max_subarray(A)

int main()
{
int arr[5]={-2,5,-1,7,-3};
int i,j,k,counter,sum,l,m,temp;
temp=0;
int n;
for(i=0;i<5;i++)
{
counter=-1;
for(j=0;j<=i;j++)
{
counter++;
k=counter;
sum=0;
for(l=0;l<5-i;l++)
{
sum=sum+arr[k];
k=k+1;
}
printf("%d",sum);
if(sum>temp)
{
temp=sum;
}
}
}


printf(" biggest sum from give array:=>%d",temp);
return 0;
}

long ConsecutiveLargestSum(vector<long>& data, vector<long>& result)
{
	long max_ending_here = 0, max_so_far = 0;
	vector<long>::iterator start, end;
	for (vector<long>::iterator it = data.begin(); it != data.end(); it++) {
		max_ending_here += *it;
		if (max_ending_here < 0) {
			max_ending_here = 0;
			start = end = data.begin();
		}
		if (max_so_far < max_ending_here) {
			max_so_far = max_ending_here;
			if (start == data.begin())
				start = it;
			end = it;
		}
	}
	result.assign(start, end + 1);
	return max_so_far;
}

slick python solution

def max_list(arr):
	i,j,s,mi,mj,ms = 0,0,0,0,0,0
	for i in xrange(len(arr)):
		s += arr[i]
		if s <= 0:
			j = i+1
			s = 0
		if s > ms:
			ms = s
			mi,mj = i,j
	return arr[mj:mi+1]
print max_list([-2,5,-1,7,-3])

def max_list(arr):
	i,j,s,mi,mj,ms = 0,0,0,0,0,0
	for i in xrange(len(arr)):
		s += arr[i]
		if s <= 0:
			j = i+1
			s = 0
		if s > ms:
			ms = s
			mi,mj = i,j
	return arr[mj:mi+1]
print max_list([-2,5,-1,7,-3])

We can first sort the list and can take the last two integers ....

Recursive Approach:

from sys import maxint

def max_subarray(A):
    if not A:
        return -maxint

    max_sub = A[0]
    sum_subarray = 0

    for i in range(len(A)):
        sum_subarray += A[i]
        if sum_subarray < 0:
            break
        if max_sub < sum_subarray:
            max_sub = sum_subarray


    return max(max_sub,max_subarray(A[i+1:]))

A = [-3,20,50,300,-400,80,10,-4]
print max_subarray(A)
A = [-3,-5,-4]
print max_subarray(A)
A = [-3,20,50,-400,80,10,-4]
print max_subarray(A)
A = [-3,20,50,-40,80,10,-4]
print max_subarray(A)
A = [-30,20,50,-400,80,10,10,-400,100,20,-40]
print max_subarray(A)

Are you talking about the abs max sum?
Cause in the example 5 -17 gives you -12 where as -2 5 gives you 3.
And so the biggest sum would be due to -2 5 .

Here is a simple approach

public static int kadane(int[] a){
        int maxTillNow = a[0];
        int overallMax = 0;
        for(int i=1;i<a.length;i++){
            if(maxTillNow+a[i]>0)
                maxTillNow += a[i];
            overallMax = Math.max(maxTillNow,overallMax);
        }
        return overallMax;
    }

Here is a simple approach

public static int kadane(int[] a){
        int maxTillNow = a[0];
        int overallMax = 0;
        for(int i=1;i<a.length;i++){
            if(maxTillNow+a[i]>0)
                maxTillNow += a[i];
            overallMax = Math.max(maxTillNow,overallMax);
        }
        return overallMax;
    }

public static void main(String args[]){
        
		int[] arr = {-2,5,3,-1,7,-3};
		int arrLen = arr.length;
		int maxSum = 0;
		String str ="";
		String maxStr = "";
		for (int i = 2; i <= arrLen; i++){
			for (int j=0; j< arr.length; j++){
				int temp =0;
				int k = j;
				str ="";
				while (k < j+i && (j+i <arrLen)){
					temp += arr[k];
					str = str + " " + arr[k];
					k++;
				}
				if (temp > maxSum){
					maxSum = temp;
					maxStr = str;
				}
			}
		}
		System.out.println("Sum : " + maxSum);
		System.out.println(maxStr);
	}