CareerCup

Code looks a bit tough for understanding and massive, but the sense is simple: we keep counters for sum (current and maximum) and indices of range (current and maximum), As maximum sum exceeds current one - we remember new indices as maxumum ones. The special case is tail - after iteration we must check the last element.

public static int[] findLargestSubarray(int[] array) {
        int curSum = 0, curStart = -1;
        int maxSum = 0, maxStart = -1, maxEnd = -1;

        for (int i = 0; i < array.length; i++) {
            if (array[i] > 0) {
                if (curStart < 0) {
                    // We only came to next sequence of positive numbers, lets' store the start idx (inclusive)
                    curStart = i;
                }
                curSum += array[i];
                if (curSum > maxSum) {
                    // update max indices
                    maxSum = curSum;
                    maxStart = curStart;
                }
            } else {
                if (curStart >= 0 && maxStart == curStart) {
                    // we just left the maximum sequence, let's remember ending index (exclusive)
                    maxEnd = i;

                }
                // reset fields
                curSum = 0;
                curStart = -1;
            }
        }
        // Special case for last element (don't forget about tail!)
        if (array[array.length - 1] > 0 && curStart >= 0 && maxStart == curStart) {
            maxEnd = array.length;
        }
        if (maxStart < 0) {
            return new int[]{};
        }
        return Arrays.copyOfRange(array, maxStart, maxEnd);
    }

    public static void main(String[] args) {
        int[] largestSubarray = findLargestSubarray(new int[]{2, 5, 1, -1, -2, 8, 9});
        assert Arrays.equals(largestSubarray, new int[]{8, 9}) : Arrays.toString(largestSubarray);
        int[] largestSubarray1 = findLargestSubarray(new int[]{-1, -3, -6, -2, -9});
        assert Arrays.equals(largestSubarray1, new int[]{}) : Arrays.toString(largestSubarray);
        int[] largestSubarray2 = findLargestSubarray(new int[]{-9, 3, 2, 3, -4, 4, 3});
        assert Arrays.equals(largestSubarray2, new int[]{3, 2, 3}) : Arrays.toString(largestSubarray);
    }

A nice and simple one, just need to consider all the edge cases. for eg. what if all elements are negative/zero. A single traverse would be enough while storing the start and ending index of continuous positive elements and their current sum.

My c++ implementation is :

void printSubset(int arr[],int n)
{
    int i,sum=INT_MIN,current=0,start=0,end=0,s,e;
    for(i=0;i<n;)
    {
        s=i;
        while(i<n && arr[i]>0)
        {
            current+=arr[i];
            i++;
        }
        e=i-1;
        if(sum<current)   // update indices if current sum exceeds the total one
        {
            sum=current;
            start=s;
            end=e;
            current=0;
        }

        i++;
        while(i<n && arr[i]<=0)    //  find the next positive number 
            i++;
    }

    if(end==-1) 	cout<<"All are negative or zero";
    else	cout<<start<<" "<<end;
}

Python solution, probably doesn't cover all edge conditions though.
Simple idea: find the positive subarrays, and compare them..

def cont_pos_subarray(idx,arr):
  subarray = []
  last_num = arr[idx]
  if (last_num > 0):
    subarray.append(last_num)
  end_index = idx
  for i in range(idx+1,len(arr)):

    if arr[i] > last_num:
      last_num = arr[i]
      subarray.append(last_num)
    else:
      end_index = i
      break
    if i == len(arr) -1:
      end_index = i
  return (subarray, end_index)

def subarrays(arr):
  i = 0
  arrays = []
  while (i < (len(arr)-1)):
    subarray, end_index = cont_pos_subarray(i,arr)
    print subarray
    arrays.append(subarray)
    i = end_index
  return arrays

def highest_sum_subarray(array):
  max_arr = []
  for arr in subarrays(array):
    if (sum(arr)> sum(max_arr)):
      max_arr = arr
  return max_arr

if __name__ == "__main__":
  arr = [1,2,5,-7,2,5]
  print(cont_pos_subarray(0, arr))
  print(cont_pos_subarray(3, arr))
  print(subarrays(arr))
  print(highest_sum_subarray(arr))

DP Solution... Store the max sum and no. elements included in the sum in a two dimensional array.

int[][] subseqSum = new int[arr.length][2];
		subseqSum[0][0] = arr[0];
		subseqSum[0][1] = 0;
		
		for(int i = 1; i < arr.length; i++){
			if(arr[i] < 0) {
				subseqSum[i][0] = arr[i];
				subseqSum[i][1] = 0;
				
			}
			else{
				if(subseqSum[i-1][0] >=  0){
					subseqSum[i][0] = subseqSum[i-1][0] + arr[i];	
					subseqSum[i][1] = subseqSum[i-1][1] + 1;
					
				}else{					
					subseqSum[i][0] = arr[i];
					subseqSum[i][1] = 1;
				}
				
			}
			
		}

public static void largerSubArray(int[] arr){ 
		int firstSum = 0; // sum of first subArray
		int nextSum = 0; // sum of next subArray
		int i = 0;
		
		while(arr[i] < 0 && i < arr.length){ // edge case --> if index 0 has a -ve num
			i++;
		}
		
		int firstStart = i; // start index of first subArray
		while (arr[i] >= 0 && i < arr.length) {
			firstSum += arr[i];
			i++;
		}
		int firstEnd = i;
		i++;
		
		int nextStart = i; // // start index of next subArray
		while(i < arr.length) {
			nextSum += arr[i];
			i++;
		} 
		int nextEnd = i;
		
		if (firstSum > nextSum){
			int[] firstSubset = Arrays.copyOfRange(arr, firstStart, firstEnd);
			System.out.println(Arrays.toString(firstSubset));
		} else {
			int[] nextSubset = Arrays.copyOfRange(arr, nextStart, nextEnd);
			System.out.println(Arrays.toString(nextSubset));
		}
	}

public static int[] findLargestSum(int[] arr){
		int cSum = 0, maxSum = 0;
		int startI = 0;
		int endI = 0;
		int maxStart =0, maxEnd=0;
		for (int i = 0; i < arr.length; i++){
			
			if (cSum == 0){
				startI = i;
			}
			
			if (arr[i] >= 0){
				cSum += arr[i];		
				endI = i;
				if (cSum > maxSum){
					maxStart = startI;
					maxSum = cSum;
					maxEnd = endI;
				}
			}
			else {
				cSum = 0;
			}			
		}
		if (endI == 0){ return new int[0];}
		return Arrays.copyOfRange(arr, maxStart, maxEnd+1);
		
	}

The idea is to find all the subsets of array and if the sum is greater return the subset. Only drawback is it uses extra space for storing two arraylists.

public static List<Integer> largestSubset(int[] ar) {
		List<Integer> temp = null;
		int n = ar.length;
		int max = 0;
		List<Integer> templist;
		for (int i = 1; i < n; i++) {
			int j = 0;
			templist = new ArrayList<Integer>();
			while (j < n) {
				while (templist.size() <= i) {
					templist.add(ar[j]);
					j++;
				}
				int tempSum = arraySum(templist);
				if (max < tempSum) {
					max = tempSum;
					temp = new ArrayList<Integer>(templist);
				}
				templist.remove(0);
			}
		}
		return temp;
	}
public static int arraySum(List<Integer> ar) {
		int sum = 0;
		for (int temp : ar)
			sum += temp;
		return sum;
	}

Here is dynamic programming recursive formula...
Lets take an two dimensional array R[n][n] to store the subsets sums.
Lets A is the given array.

sum_all(A[i...j]) = returns sum of all elements of A from i to j.
max_store(...) = return max sum and reserve the indexes of mx sum within the frame of (i, j).

0 < i < j < n
if(i > j) {
    return 0;
} else if (i == j) {
    return (R[i][j] = A[i]);
} else {
    R[i][j] =  max_store(S(i+1, j-1), S(i, j-1), S(i+1, j), sum_all(i, j));
    return R[i][j];
}

Considering all the boundary cases

l=[1,2, 8, -7, 2,12,-7,13]
currsum=currst=currend=maxsum=prevst=prevend=0
for i in range(0,len(l)):
  if l[i]>0:
    if currsum==0:
      currst=i
      currend=i
    else:
      currend=i
    currsum+=l[i]
  else:
    if maxsum<currsum:
      maxsum=currsum
      prevst=currst
      prevend=currend
      currsum=0
if maxsum<currsum:
  maxsum=currsum
  prevst=currst
  prevend=currend
print maxsum,"=>",l[prevst:prevend+1]

output=>>
14 => [2, 12]

public static Integer[] continuousPositive(Integer[] array) {

Integer maxSum = 0;
Integer startPoint = 0;
Integer endPoint = 0;

for(int i= 0; i<array.length; i++) {
boolean foundNegative = false;
int j = i;
Integer sum = 0;
while(i<array.length && !foundNegative) {
if(array[i] > 0) {
sum += array[i];
++i;
} else {
if(sum > maxSum) {
startPoint = j;
endPoint = i;
maxSum = sum;
}
++i;
foundNegative = true;
}
}
}
return Arrays.copyOfRange(array,startPoint,endPoint);

}

Since we're looking for a subarray with positive numbers we can easily do this in linear time.
This should cover all the border cases:
1. If the number is negative, reset the counters
2. If the number is positive, update the current counter and if need be update the max.

pair<int,int> maxContinuousSubarray(vector<int> v){
	if(v.size()==0)
		return make_pair(-1,-1);
	int maxSoFar = 0, maxCur = 0;
	int maxStart = -1, maxEnd = -1;
	int maxStartCurrent = 0;

	for(int i = 0; i < v.size(); i++){
		if(v[i] < 0){
			maxStartCurrent = i+1;
			maxCur = 0;
		} else {
			maxCur+=v[i];
			if(maxCur > maxSoFar){
				maxStart = maxStartCurrent;
				maxEnd = i;
				maxSoFar = maxCur;
			}
		}
	}
	return make_pair(maxStart,maxEnd);
}

#include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int> v ;
int n=0;
cout << " Enter total number of integers : " << endl;
cin >> n;
cout << " Enter " << n << " positive and negative numbers : " ;
int temp_sum = 0, max_sum =0, start_index = -1, end_index = -1, temp_start_index = 0;
for(int i=0; i<n; i++) {
int num = 0;
cout << endl << i << "th number : ";
cin >> num;
v.push_back(num);
if(num >=0) {
temp_sum = temp_sum + num;
if(max_sum < temp_sum) {
max_sum = temp_sum;
end_index = i;
start_index = temp_start_index;
}
}
else {
temp_sum = 0;
temp_start_index = i + 1;
}
}

cout << " Subarray with max sum : " << endl;
for(int i = start_index; i <= end_index; i++) {
cout << v[i] << " ";
}
return 0;
}