CareerCup

// example 4,-9,3,-2,4,-12
//intial max sum = 4
//2nd time max sum = 4-9 = -5 < 0 so {4,-9} couldn't be a seq or max sum so start finding sequence max sum from 3 now. (remember 4 as a oldsequenc sum)
// now start with 3 < 4 continue still 4 maxsumsubsequence wins
// now 3-2 = 1 < 4 still 4 wins as a max seq
// now 3-2+4= 5 , but now 4 < 5 so 5 will be new max sum subsequence
public void GetMaxSubSequenceSum()
{
List<int> MaxsumSeq = new List<int>();

int prevsum = 0;
int maxsum = 0;//afte adding next element

for (int i = 0; i < elements.Length; i++)
{
maxsum += elements[i];//afte adding next element

if (prevsum < maxsum)
{
//once you find that nw sequence that you generating has max sum take it as a new max sum
// and compare for a next sequence if you have a new window

prevsum = maxsum;
}
else if (maxsum < 0)
{
//if seqsum < 0 then start a new sequence from scratch
maxsum = 0;
}
}
}

Here Is O(n) solution.

/* 
 * File:   main.cpp
 * Author: vsirohi
 *
 * Created on September 8, 2012, 8:21 PM
 */

#include <cstdlib>
#include<iostream>
using namespace std;
int max(int a , int b)
{
    if(a>b)
        return a;
    else
    return b;
}
int  greatestsumarraysum(int array[], int length)
{
    int  maxsum=0, sumsofar = 0;
    int start =0, end=0;
    for(int i=0; i<length; i++)
    {
        if(array[i]> maxsum+array[i])
        {start = i;end = i;}
        maxsum = max(array[i], maxsum+array[i] );
        if(sumsofar<maxsum)
        {
            end = i;
        }
        sumsofar = max(sumsofar, maxsum);
     }
   if(sumsofar<0){
       cout<<"Error : Invalid Sum "<<endl;
        return -1;
    }
    else{
        /// print the sub array. from range start to end.
    cout<< " the max sum array is : "<<endl;
    for(int k = start; k<=end; k++)
    {
       cout<<" "<<array[k]<<" "; 
    }
  return sumsofar;
    }
}
/*
 * 
 */
int main(int argc, char** argv) {


    int arr[7] = {-5, 3, -2, -2, 6, 3, 4};
    int sum=0;
    sum = greatestsumarraysum(arr, 7);
    cout << " the sum is  : "<<sum<<endl;
        return 0;
}

This is a DP problem called maximum subarray (check wikipedia for that problem), here's modified version for Kadane's algorithm which stores array indexes of the maximum subarray:

/**
	 * @author Ahmed Fahim
	 * Created on October 4, 2012, 058:20 AM
	 */
	public static int[] maxSubarray(int A[]) {
		int max_so_far = 0;
		int max_ending_here = 0;
		int start = 0;
		int end = 0;
		
		for (int i = 0; i < A.length; i++) {
			if (max_ending_here + A[i] > 0) {
				max_ending_here = max_ending_here + A[i];
				start = min(start, i);
			} else {
				max_ending_here = 0;
				start = i+1;
			}
			
			if (max_ending_here > max_so_far) {
				end = i;
				max_so_far = max_ending_here; 
			}
		}
		
		return Arrays.copyOfRange(A, start, end + 1);
	}
	
	public static int max(int x, int y) {
		return x >= y
			? x
			: y;
	}
	
	public static int min(int x, int y) {
		return x <= y
			? x
			: y;
	}

def get_largest_sum_subarray(array):
	assert len(array) > 1
	max_sum = second_max_sum = current_sum = array[0]
	start = end = 0
	
	for i in range(1, len(array)):
		if current_sum < 0:
			current_sum = 0
			start = i
		current_sum += array[i]
		if current_sum > max_sum:
			second_max_sum = max_sum
			max_sum = current_sum
			end = i
		elif current_sum > second_max_sum:
			second_max_sum = current_sum
			
	if max_sum < -1:
		raise Exception("max sum is less than 1")
		
	if start == 0 and end == len(array) - 1:
		max_sum = second_max_sum
		
	return max_sum

/*Time complexity = O(n)*/
#include<iostream>
#include<malloc.h>

using namespace std;

int *repeat(int *a,int start,int n)
{
	int i,cstart=0,pstart=0,end=0,*ret;
	ret = (int*)malloc(3*sizeof(int));
	int sum=0,sm=-999;
	for(i=start;i<n;i++){
		if((sum <= 0) && (a[i]>=0)){
	   		sum = a[i];
	   		cstart = i;	
	   	} 
		else sum+=a[i];
		if(sum>sm) {
			sm = sum;
			end =i;
			pstart = cstart;
		}
		
	}
	ret[0]=sm;
	ret[1]=pstart;
	ret[2]=end;
	return ret;
}

void largest_sum_subarray(int *a,int n)
{
	int *ret,**comp,i;
	ret = (int*)malloc(3*sizeof(int));
	comp= (int**)malloc(2*sizeof(int*));
	for(i=0;i<3;i++){
		comp[i] = (int*)malloc(3*sizeof(int));
	} 
	ret = repeat(a,0,n);	
	if( ret[1] == 0 && ret[2] == n-1){
		comp[0] = repeat(a,0,n-1);
		comp[1] = repeat(a,1,n);
		if(comp[0][0] > comp[1][0]) {
			for(i=comp[0][1];i<=comp[0][2];i++) cout<<a[i]<<" ";
		}
		else{
			for(i=comp[1][1];i<=comp[1][2];i++) cout<<a[i]<<" ";
		}
	}
	else{
		if(ret[0] < 0 ) cout<<"Largest sum is <=  -1\n";
		else{
			for(i=ret[1];i<=ret[2];i++) cout<<a[i]<<" ";
		}
	}
	cout<<endl;
}

main()
{
	int n,i;
	cout<<"enter size\n";
	cin>>n;
	int *a = new int[n];
	cout<<"enter array\n";
	for(i=0;i<n;i++) cin>>a[i];
	largest_sum_subarray(a,n);
	
}

//dynamic progrming
public void GetMaxSubSequenceSumDynamicprog()
{
//maxsum [i] = Max ( maxsum(i-1) + A[i], A[i])
int maxsum = 0;
//int prevsum;
for (int i = 0; i < elements.Length -1; i++)
{
//prevsum = maxsum;
maxsum += elements[i];
maxsum = Math.Max(maxsum, elements[i]);
}
}

Kadane's solution... O(n) time/O(1) space

int a[]={4,-1,2,1,8,-6,-1,3};

int sum(int start,int end)
{
        if(start==end) return a[start];
        else return a[start]+ sum(start+1,end);
}

find(int* start,int* end,int arr_start,int arr_end)
{
        if (arr_start==arr_end)
        {
                *start = arr_start;
                *end   = arr_end;
                return;
        }
        int start1, start2, end1, end2;
        // devide the arrays into half and find the longes sequnce
        find(&start1,&end1,arr_start,(arr_start+arr_end)/2);    //1st half
        find(&start2,&end2,(arr_start+arr_end)/2+1,arr_end);    //2nd Half

        int sum_area_1,sum_area_2,sum_both1_and_2;
        sum_area_1 = sum(start1,end1);
        sum_area_2 = sum(start2,end2);
        sum_both1_and_2 = sum(start1,end2);


        //compare the longest sums and decide start and end
        if(sum_area_1>sum_area_2 && sum_area_1>sum_both1_and_2 )
        {
                *start = start1;
                *end = end1;
                return;
        }
        if(sum_area_2>sum_area_1 && sum_area_2>sum_both1_and_2 )
        {
                *start = start2;
                *end = end2;
                return;
        }
        if(sum_both1_and_2 >sum_area_2 && sum_both1_and_2>sum_area_1 )
        {
                *start = start1;
                *end = end2;
                return;
        }

}

main()
{
        int start,end;
        find(&start,&end,0,7);
        printf("%d,%d,%d\n",start,end,sum(start,end));
}

if there is atleast one +ve no in the array then maximum sum subarray cant be -ve sum,,
and you mentioned this is array of +ve and -ve no , so it is a simple dp problem..

void f(int* a)
{
    int gs, gsx, gsy, cs, csx, csy;
    gs = INT_MIN; // global sum
    cs = 0;       // current sum
    csx = csy = gsx = gsy = -1; // csx: current sum starting X,...

    for(int i=0;i<len(a);++i)
    {
        cs+=a[i];
        csy = i;
        if(csx<0)
        {
            csx = i;
        }

        if(cs>gs)
        {
            gs = cs;
            gsx = csx;
            gsy = csy;
        }

        if(cs<=0)
        { 
            cs = 0;
            csx = csy = -1; 
        }
    }   

    if(gs < -1)
       throw;
    else
       printf("gs: %d, gsx:%d, gsy:%d", gs, gsx, gsy);
}

subsequence or subarray?

/* find subarray of max sum, O(n), dont return whole array
 */

#include <stdio.h>
#include <assert.h>

#define N 10

struct result {
        int max_sum;
        int start_i;
        int end_i;
};

struct result *find_maxsubarr(int *arr, struct result *r)
{
        int i = 0, max, j = 0, first, last;
        int sum = 0;

        max = sum = r->max_sum = arr[i];
        first = last = r->start_i = r->end_i = i;

        for(j = i+1; j< N; j++)
        {
                sum += arr[j];
                if(sum < 0) {
                        while(arr[j] <= 0) { j++;}
                        i = j;
                        first = i;
                        last = i;
                        sum = arr[i];
                }
                else if(sum > max) {
                        max = r->max_sum = sum;
                        last = r->end_i = j;
                        r->start_i = first;
                }
        }

        /*dont return whole array, whole array 
          will be included only if there are +ve
          numbers at both ends. substract the min
          of them */
        if((last - first) == N-1){
                // find first -ve integer after a[0]
                i = 1; sum = r->max_sum - arr[0];
                while(arr[i] <= 0) {
                        sum -= arr[i];
                        i++;
                }
                // find first -ve integer before a[N-1]
                j = N-2;
                int sum2 = r->max_sum - arr[N-1];
                while(arr[j] <= 0) {
                        sum2 -= arr[j];
                        j--;
                }
                if(sum >= sum2) {
                        r->max_sum = sum;
                        r->start_i = i;
                }
                else {
                        r->max_sum = sum2;
                        r->end_i = j;
                }
        }

        assert(r->max_sum >= 0);
        return r;
}

int main()
{
        int arr[N] = {22, -16, 5, -1, 12, -3, 8, -1, 16, 12};
        struct result r;

        if(N>1)
                find_maxsubarr(arr, &r);
        else
                printf("array len less than 2\n");
        printf("max:  %d\n", r.max_sum);
        printf("first_index:  %d\n", r.start_i);
        printf("last_index:  %d\n", r.end_i);

        return 0;
}

Solution O(n) time and space →
1.) sum the elements from left to right in same or other array a[].
2.) in a new array b[] from left to right keep the index of the smallest element.
3.) the reslt is the max(a[i] - a[b[i - 1]])

public void maxSumSubArr(int[] a) {
  if (a == null || a.length == 0)
   System.out.println(-1);
 
  //1
  for (int i = 1; i < a.length; i++)
   a[i] += a[i-1];
    
  //2
  int[] b = new int[a.length];
  for (int i = 1; i < b.length; i++)
   if (a[b[i - 1] > a[i] )
    b[i] = i;
   else
    b[i] = b[i - 1];
  
  //3.
  int maxSum = a[0];
  int idxStart = 0;
  int idxEnd = 0;
  for (int i = 1; i < a.length; i++)
   if (maxSum < a[i] - a[b[i - 1]]) {
    maxSum = a[i] - a[b[i - 1]];
    idxStart = b[i - 1];
    idxEnd = i;
   }
  
  //Print results
  System.out.format(“Max Array: startIdx is %s, endIdx is %s, sum is %s”, idxStart, idxEnd, maxSum);
 }

/*
 * By : Bilal Alqudah (C)
 */
public class BigSum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		 
		int[] values= {10,20,5,-20,-50,10,-5,100,10,-5,20,200,-20};
		LocatorObject tempObj= new LocatorObject();          // temporary holder for the values
		LocatorObject finalResult= new LocatorObject();      // the final result holder
 
		tempObj.s=0;    
		tempObj.e=0;   
		
		for(int i=0; i< values.length;i++){
		tempObj.sum+=values[i];
		if (tempObj.sum>=finalResult.sum){
			tempObj.e=i;
			//copy the values to the last result object.
			finalResult.sum=tempObj.sum;
			finalResult.s=tempObj.s;
			finalResult.e=tempObj.e;
		}else{
			if(values[i]<0){
			// reset all values if the number caused the sum to go down! 
			  tempObj.s=i+1;
			  tempObj.e=i+1;
			  tempObj.sum=0;
			}
		}
		System.out.println("O2: "+finalResult.toString()+" , O1: "+tempObj.toString());
		}
		System.out.println("---------------------");
		System.out.println(finalResult.toString());
		
	}
	

}
class LocatorObject  {
	int s=0;
	int e=0;
	int sum=0;
	public LocatorObject(){
		
	}
	public String toString(){
		return ("SUM["+s+","+e+"]="+sum);
	}
 }

isit longest subsequence problem...? i saw same q' in the forum..

/**
	 * Description:
	 * Method finds the largest subset sum of a given array as follows:
	 * 1. create an array with the sums of all of the elements except the first
	 * 2. create an array with the sums of all of the elements except the last
	 * 3. find the max some of both, get that index
	 * 4. travel from index backwards to the first negative sum
	 * 5. the largest sum is the sum of the elements between the to indexes (the negative sum's index not included)
	 * 
	 * @param array
	 * @return
	 */
	public static int maxSubsetSum(int[] array)
	{
		int[] sumMinusFirst = new int[array.length -1];
		int[] sumMinusLast = new int[array.length -1];
		
		sumMinusLast[0] = array[0];
		for(int i = 1; i < array.length - 1; i++){
			sumMinusLast[i] 	= array[i] + sumMinusLast[i-1];
			sumMinusFirst[i-1] 	= array[i] + ((i==1) ? 0 : sumMinusFirst[i-2]);
		}
		sumMinusFirst[sumMinusFirst.length-1] = 
				sumMinusFirst[sumMinusFirst.length-2] + array[array.length-1];
		
		int max = array[0];
		int endIndex = 0;
		boolean isWithoutLast = true;
		
		for(int i = 0; i < sumMinusFirst.length; i++){
			if(max < sumMinusFirst[i] ||  max < sumMinusLast[i]){
				endIndex = i;
				max = Math.max(sumMinusFirst[i], sumMinusLast[i]);
				isWithoutLast = (max == sumMinusLast[i]);
			}
		}
		
		int[] sums = isWithoutLast ? sumMinusLast : sumMinusFirst;
		int startIndex = endIndex;
		while(startIndex >= 0 && sums[startIndex--] > 0);
		endIndex += isWithoutLast ? 0 : 1;
		int largestSum = 0;
		for(int i = startIndex+2; i <= endIndex; i++)
			largestSum += array[i];
		
		return largestSum;
	}

// Longest Sum Subsequence
	public int find_Longest_Sum_Subsequence(int[] array)
	{
		// return Integer.Min_value if the input array is null
		if (array == null)
			return Integer.MIN_VALUE;
		if (array.length == 1)
			return array[0];
		
		int longest_sum = array[0];
		int build_sum = array[0];
		int counter = 1;
		while (counter < array.length)
		{
			if ((build_sum+array[counter])>0)
				build_sum += array[counter++];
			else
				build_sum = array[counter++];
			if (build_sum > longest_sum)
				longest_sum = build_sum;
		}
		return longest_sum;
	}

/**
 * Program print the maximum sub sequence sum in the array
 * and prints the start and end indices of the sub sequence
 * 
 * If all the elements in the array are negative
 * max sub sequence sum is 0
 * 
 */
public class LargestSumContigiousSubsequence {

	public static void main(String[] args) {
		int[] a = { -2, 11, -4, 13, -5, 2 };

		int maxSum = 0;
		int thisSum = 0;

		int sIndex = 0;
		int eIndex = 0;

		for (int i = 0; i < a.length; i++) {

			if (thisSum == 0) {
				sIndex = i;
				eIndex = i;
			}
			thisSum += a[i];

			if (thisSum > maxSum) {
				maxSum = thisSum;
				eIndex++;
			}
			if (thisSum < 0) {
				thisSum = 0;
			}
		}

		System.out.println("max sum:" + maxSum);
		if (maxSum > 0) {
			System.out.println("start index :" + sIndex + " eIndex :" + eIndex);
		}

	}
}

Here is my way of finding the largest sum

int largest_sub_arr(int *data, unsigned size){
    int past = data[0];
    int future = data[0];
    int temp = -1; 
    int i;
    int start_pos = 0, end_pos = 0;

    for(i = 1; i < size; i++)
    {   
        future += data[i];
        if (future < 0 ){
            future = 0;
            start_pos = i+1;
        }   
        if (future  > past){
            past = future;
            end_pos = i;
        }   
    }   
    printf("MAX:%d START:%d END:%d\n",past, start_pos, end_pos);
    

    return past;
}

#include <iostream>
using namespace std;

struct Subset {
  int start, end, sum;
};

int advanceTillPositive( int *arr, int N, int i ) {
  // no checks
  while ( i < N && arr[i] <= 0 ) {
    i++;
  }
  return i;
}

Subset getSubset( int *arr, int N, int* iPtr ) {
  // no checks
  // assumes a[i] = positive
  int& i = *iPtr;
  Subset subset;
  subset.start = subset.end = i;
  subset.sum = arr[i];
  i++;
  while ( i < N && arr[i] >= 0 ) {
    subset.sum += arr[i];
    subset.end += 1;
    i++;
  }
  return subset;
}

int advanceTillPositive( int* arr, int N, int i, int* ptrSum ) {
  int& sum = *ptrSum;
  while ( i < N && arr[i] < 0 && sum > 0 ) {
    sum += arr[i];
    if ( sum < 0 ) {
      return i - 1;
    }
    i++;
  }
  return i - 1;
}


int getLargestSubsetSum( int *arr, int N ) {
  if ( arr == NULL ) {
    return -1;
  }

  int i = 0;
  i = advanceTillPositive( arr, N, i );
  if ( i >= N ) {
    return -1;
  }
  Subset maxSubset;
  maxSubset = getSubset( arr, N, &i );
  i = maxSubset.end + 1;
  if ( i >= N ) {
    return maxSubset.sum;
  }
  while ( i < N ) {
    int sum = maxSubset.sum;
    i = advanceTillPositive( arr, N, i, &sum );
    if ( i == N - 1 ) {
      break;
    }
    i++;
    if ( arr[i] <= 0 ) {
      i = advanceTillPositive( arr, N, i );
      if ( i >= N ) {
        break;
      }
      Subset tmp = getSubset( arr, N, &i );
      if ( tmp.sum > maxSubset.sum ) {
        maxSubset = tmp;
      }
    } else {
      Subset tmp = getSubset( arr, N, &i );
      maxSubset.sum = sum;
      maxSubset.sum += tmp.sum;
      maxSubset.end = tmp.end;
    }
  }

  cout << "Max start: " << maxSubset.start << endl;
  cout << "Max end  : " << maxSubset.end << endl;
  cout << "Max sum  : " << maxSubset.sum << endl;
  return maxSubset.sum;
}

void display( int *arr, int N ) {
  if ( NULL == arr ) {
    cout << "NULL!" << endl;
  }
  for ( int i = 0; i < N; i++ ) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

void test() {
  int arr1[5] = { 3, 4, -5, -1, 7 };
  int arr2[4] = { 3, 4, -8, 7 };

  cout << "Array: "; display( arr1, 5 );
  cout << "Largest Subset Sum: " << getLargestSubsetSum( arr1, 5 ) << endl;
  
  cout << "Array: "; display( arr2, 4 );
  cout << "Largest Subset Sum: " << getLargestSubsetSum( arr2, 4 ) << endl;
}

int main() {
  test();
  return 0;
}

Hi Guys,

I had wrote the function to find the max sum subarray. This is working fine for me.

public static int FindMaxSubArraySum(int[] arr)
        {
            int startIndex = -1;
            int endIndex = -1;
            int sumofPositiveNums = 0;
            int sumofNegativeNums = 0;

            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] > 0 || startIndex != -1)
                {
                    if (arr[i] <= 0)
                    {
                        sumofNegativeNums += arr[i];
                    }
                    else
                    {
                        if (startIndex == -1) startIndex = i;
                        else endIndex = i;
                        sumofPositiveNums += arr[i] + sumofNegativeNums;
                        sumofNegativeNums = 0;
                    }
                    if ((sumofNegativeNums * -1) >= sumofPositiveNums)
                    {
                        startIndex = -1;
                        endIndex = -1;
                        sumofPositiveNums = 0;
                        sumofNegativeNums = 0;
                    }
                }
            }

            return sumofPositiveNums;
        }

simply print the sum of all +ve numbers in the array .
it wont work for one case:
If all the numbers are negative. In ths case print the largest one.

public class PositiveNegativeSubsequence {

public static void main(String[] args)
{
int[] input = new int[]{-1,1,2,-1000,5,-1,-2,3,100,-1,5,5,3};

System.out.println(Arrays.toString(input));

System.out.println(Arrays.toString(LargestSubsequence(input)));
}

private static int[] LargestSubsequence(int[] input)
{
int bound1 = 0;
int bound2 = 0;

int j = 0;

int MaxSum = 0;
int sum = 0;

boolean NegativeMet = false;

boolean PositiveMet = false;

//ignoring first negative values

while(input[j] <= 0)
{
j++;
}

bound1 = j;
bound2 = j;

for (int i = j; i < input.length-1; i++) {

if(!NegativeMet && (input[i+1] < 0)) // aucun nombre negative trouve et le prochain et negative
{
//System.out.println("Transition + -> - here: " + input[i] + " " + input[i+1]);

NegativeMet = true;
sum += input[i];
}
else if(NegativeMet && !PositiveMet && (input[i+1] > 0)) //on a vu un negative et le prochain et poistive
{
//System.out.println("Transition - -> + here: " + input[i] + " " + input[i+1]);

PositiveMet = true;
sum += input[i];
bound2 = i;
}

if (PositiveMet && NegativeMet) {

if(sum <= 0)
{
bound1 = i+1;
bound2 = i+1;
sum = 0;
}
else
{
if(sum > MaxSum)
{
MaxSum = sum;
}
}
NegativeMet = false;
PositiveMet = false;
}

}

if(!NegativeMet)
{
bound2 = input.length;
}

System.out.println("SUM = " + sum);

return Arrays.copyOfRange(input, bound1, bound2);
}

}