CareerCup

1. To find maximum sum SUBSET: eliminate all negative integers, keep only positive ones. If all numbers are negative, choose the empty subset.

2. To find maximum sum of continuous subsequence: keep summing up numbers and record maximum sum. If the sum is negative, reset it to be 0.

sum = 0;
maxSum = 0;
for i = 1..n
	sum += array[i];
	maxSum = max (maxSum, sum);
	if (sum<=0) sum = 0;

Does it have to be a continuous subsequence?
If so, there is a linear time solution to this. You might want to lookup max subarray/ Kadane's algo

The maximum subset with negative set of integers can be found out by first eliminating negative numbers and then finding out maximum subset using Kadane's algorithm. If all the numbers are negative that is the sum <= 0 then return 0 as described above

This was pretty much copied and pasted from the wikipedia page for Maximum_subarray_problem:

private int LargestSum(int[] numbers)
{
	if (numbers == null || numbers.Length == 0)
	{
		return 0;
	}

	int max_so_far = numbers[0];
	int max_ending_here = numbers[0];

	for (int i = 1; i < numbers.Length; i++)
	{
		if (max_ending_here < 0)
		{
			max_ending_here = numbers[i];
		}
		else
		{
			max_ending_here += numbers[i];
		}

		if (max_ending_here >= max_so_far)
		{
			max_so_far = max_ending_here;
		}
	}

	return max_so_far;
}

int max_sum(int a[],int n)
{
int max=a[0], curr=0;
for(int i=0;i<n;i++){
if(curr<0)
curr=a[i];
else
curr+=a[i];
if(max<curr)
max=curr;
}
return curr;
}

int max_sum(int a[],int n)
{
    int max=a[0], curr=0;
    for(int i=0;i<n;i++){
        if(curr<0)
        curr=a[i];
        else
        curr+=a[i];
        if(max<curr)
        max=curr;
    }
    return curr;
}

static int maxSubArraySum(int[] data){
	    int p1 = 0;
	    int max_so_far = Integer.MIN_VALUE;
	    int sum  = 0;
	    for(int i = 0; i < data.length; i++) {
	        int temp = sum + data[i];
	        if(temp > max_so_far)   max_so_far = temp;
	        if(temp < 0) {
	            sum = 0;
	        } else {
	            sum = temp;
	        }
	    }
	    return max_so_far;
	}

public int maxSubArray(int[] prices) {
        if (prices == null || prices.length < 1) {
            return 0;
        }    

        int currentMax = prices[0], max = prices[0];
        for (int i=1; i < prices.length; i++) {
            currentMax = Math.max(prices[i], currentMax+prices[i]);
            max = Math.max(max, currentMax);
        }
        return max;
   }