CareerCup

Use Kadanes algorithm to solve in O(n) time.

public static List<Integer> maxSumSubArray(int[] A)
{
	int sumSoFar = A[0];
	int maxSum = 0;
	int tempBegin = 0;
	int begin = 0;
	inr end = 0;

	for(int i=1; i<A.length; i++)
	{
		if(sumSoFar < 0)
		{
			sumSoFar = A[i];
			tempBegin = i;
		}
		else sumSoFar+=A[i];
		if(sumSoFar > maxSum)
		{
			maxSum = sumSoFar;
			begin = tempBegin;
			end = i;
		}
	}

	ArrayList<Integer> result = new ArrayList();
	for(int i=begin; i<end; i++)
		result.add(A[i]);
	return result;
}

This is solved using Kadane's algo ->O(N)

Pick all nonnegative elements. Done.

If all negative elements... And null subseq not allowed, return single element with smallest abs. Value

Hu asked you this on sunday?

Here is the solution with O(n) complexity

int sequence(int numbers[], int length)
{
// Initialize variables here
int max_so_far = numbers[0], max_ending_here = numbers[0];


int begin = 0;
int begin_temp = 0;
int end = 0;

// Find sequence by looping through
for(int i = 1; i < length; i++)
{
// calculate max_ending_here
if(max_ending_here < 0)
{
max_ending_here = numbers[i];

begin_temp = i;
}
else
{
max_ending_here += numbers[i];
}

// calculate max_so_far
if(max_ending_here >= max_so_far )
{
max_so_far = max_ending_here;

begin = begin_temp;
end = i;
}
}
return max_so_far ;
}

psuedo code for max-subarray function when the array can have positive as well as negative numbers.

tempsum = 0;
maxsum =0;

for(int i =0;i<num.length ; i++)
{
int futuresum = tempsum + num[i];
if(futuresum>0)
{
tempsum = futuresum;
if(tempsum >maxsum) maxsum = tempsum;
else tempsum =0;
}
return maxsum;
}

main()
{
// int arr[] = {2,3,-5,4,8,-2,-10,-30, 20, 30,-50,10};
int arr[] = {-2,-3,-5,-4,-8,-1,-10,-30, -20, -30,-50,-10};
int sum =-100;
int s_index =0;
int e_index =0;
int maxsum=-100;
int max_s =0;
int max_e =0;
int i;
int n = sizeof(arr)/sizeof(arr[0]);
for( i=0; i < n ; i++)
{
sum += arr[i];
if(sum > maxsum)
{
maxsum = sum;
max_e =i;
max_s =s_index;
}
else if(sum < 0)
{
sum =0;
s_index = i+1;
}
}
printf("\nOriginal Array\n");
printf("{");

for(i=0; i < n ; i++)
{
printf("%d, ", arr[i]);
}

printf("}\n");

printf("\nOP Array\n");
printf("{");

for(i=max_s; i < max_e +1 ; i++)
{
printf("%d, ", arr[i]);
}
printf("}\n");
}

#include<stdio.h>
#include<stdlib.h>
int maxSubArraySum(int *);.
int maxSubArraySum(int *arr).
{
int *sum = (int *)calloc(sizeof(int), 8);.
int i, large = arr[0];.
sum[0] = arr[0];.
for (i=1;i<8;i++)
{
if (arr[i] >= 0).

{
if (sum[i-1] < 0).
sum[i] = arr[i];.
else 
sum[i] = sum[i-1] + arr[i];.
}
if (arr[i] < 0 && (arr[i]+sum[i-1] >= 0)).
{
sum[i] = sum[i-1] + arr[i];.
}
else if(arr[i] < 0 && (arr[i]+sum[i-1] < 0 )).
{
sum[i] = arr[i];.
}
if (sum[i] > large).
large = sum[i];.
}
return large;
}

int main()
{
int arr[] = {-2,-3,4,-1,-2,1,5,-3};.
printf("Maximum sum - %d", maxSubArraySum(arr));.
getchar();
return;

}

Looks like folks need to look up definition of subsequence

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define S 6

int main()
{
	int tab[S] = {1,6,2,-10,4,2};
	int bigest = tab[0];
	int tmp = tab[0];
	vector<int> v1, v2;
	v1.insert(v1.begin(), tab[0]);
	v2 = v1;

	for (int k = 0; k < S; ++k)
	{
		tmp = tab[k];
		if (tmp > bigest)
		{
			bigest = tmp;
			v1.clear();
			v1.insert(v1.begin(), bigest);
			v2 = v1;
		}
		else
		{
			v2.clear();
			v2.insert(v2.begin(), tab[k]);
		}
		for (int j = k+1; j < S; ++j)
		{
			tmp += tab[j];
			v2.insert(v2.end(), tab[j]);
			if (tmp > bigest)
			{
				bigest = tmp;
				v1 = v2;
			}
		}
		v2.clear();
	}
	
	cout << "bigest sum : " << bigest << endl;
	for (vector<int>::iterator it = v1.begin(); it<v1.end(); ++it)
		cout << ' ' << *it << endl;

	system("pause");
	return 0;
}

i think this really should be sub array too... hmmm

private static int findSubListWithMaxSum(List<Integer> originalSequence) {
		int sum = 0;
		int maxSum = 0;

		for (int i = 0; i < originalSequence.size(); i++) {
			int currentNumber = originalSequence.get(i);
			sum = sum + currentNumber;

			if (sum < 0) {
				sum = 0;
			} else if (maxSum < sum) {
				maxSum = sum;
			}
		}

		return maxSum;
	}

std::pair<int, int> find_sub_seq(std::vector<int> &vec) {
int i_start = 0;
int i_start_tmp = 0;
int i_end = 0;
int current_sum = 0;
int sum = 0;

for (int i = 0; i < vec.size(); i++) {
current_sum += vec[i];

if (current_sum > sum) {
i_start = i_start_tmp;
i_end = i;
sum = current_sum;
}

if (current_sum <= 0) {
i_start_tmp = i + 1;
current_sum = 0;
}
}

return std::pair<int, int>(i_start, i_end);
}

///
max_subsequence(new int[] {-2,1,-3,4,-1,2,1,-5,4});

///
public static void max_subsequence(int sequence[]){
		int MAX = Integer.MIN_VALUE;

		String paths[] = new String[sequence.length];
		int sum[] = new int[sequence.length];
		for(int i = 0; i <sequence.length; i++){
			paths[i] = sequence[i] + ",";
			sum[i] = sequence[i];
			if(sum[i]>MAX){
				MAX = sum[i];
			}
		}
		
		for(int i = 1; i < sequence.length; i++){
			if((sum[i-1] + sum[i]) > sum[i]){
				paths[i] = paths[i-1] + paths[i];
				sum[i] = sum[i-1]+sum[i];
				if(MAX < sum[i]){
					MAX = sum[i];
				}
			}
		}

	for(int i = 0; i < paths.length; i++){
		if(MAX == sum[i]){
			System.out.println("["+i+"]"+ " MAX: " + paths[i] + " = " + sum[i]);
		}else{
			System.out.println("["+i+"]"+paths[i] + " = " + sum[i]);
		}
	}

	}

Output:
[0]-2, = -2
[1]1, = 1
[2]1,-3, = -2
[3]4, = 4
[4]4,-1, = 3
[5]4,-1,2, = 5
[6] MAX: 4,-1,2,1, = 6
[7]4,-1,2,1,-5, = 1
[8]4,-1,2,1,-5,4, = 5

o(n) solution:

private static int findMaximumSumSubsequence(List<Integer> list) {
int currentMax = Integer.MIN_VALUE;
int tempMax = 0;
for (Integer integer : list) {
if (integer >= 0) {
if (tempMax < 0)
tempMax = 0;
tempMax += integer;
} else {
if (tempMax > currentMax) {
currentMax = tempMax;
}
tempMax += integer;


}

}
return Math.max(tempMax, currentMax);
}

In:
numbers={-2,1,-3,4,-1,2,1,-5,4};
tmpsum=0;endsum=0;
beginCount=1;endCount=1;
For[i=1,i<=Length[numbers],i++,
For[j=i,j<=Length[numbers],j++,
tmpsum=tmpsum+numbers[[j]];
If[tmpsum>endsum,endsum=tmpsum;beginCount=i;endCount=j]
];
tmpsum=0;
];
Print["Array of numbers: "<>ToString[numbers]]
Print["Contiguous subarray with the largest sum " <> ToString[Take[numbers,{beginCount,endCount}]]<>"; sum = "<>ToString[endsum]]

Out:
Array of numbers: {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Contiguous subarray with the largest sum {4, -1, 2, 1}; sum = 6

public int[] getMaxSumSubArray(int[] a){
		
		if( a== null || a.length == 0){
			return null;
		}
		
		int n = a.length;
		
		int maxSum = 0;
		int currentSum = -1;
		int tempStart = 0;
		int start = 0;
		int end = 0;
		
		for(int i=0;i<n;i++){
			
			if(currentSum < 0){
				currentSum = a[i];
				tempStart = i;
			}else{
				currentSum+=a[i];
			}
			
			if(currentSum > maxSum){
				maxSum = currentSum;
				start = tempStart;
				end = i;
			}
		}
		
		int[] result = new int[end-start + 1];
		
		for(int i = start, j=0; i <= end; i++,j++){
			result[j] = a[i];
		}
		
		return result;
		
		
	}