CareerCup

Similar question has been solved using dynamic programming at: question?id=19378664

Follows the recursive structure:
currentSum = max{A[i], max{A[i-2] + A[i], A[i-2]}, max{A[i-3] + A[i], A[i-3]}, } // i runs from 2 to N.

Full working implementation in java is given below. Give the input numbers using space as delimiter.
Eg: 1 - 1 3 8 4
1 5 3 9 4
1 2 3 4 5

import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxSumSubset {

	static ArrayList<Integer> input = new ArrayList<Integer>();

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Pattern pattern = Pattern.compile(System.getProperty("line.separator")
				+ "|\\s");
		scanner.useDelimiter(pattern);

		int intval, tempMax = 0;

		while (scanner.hasNextInt()) {
			intval = scanner.nextInt();
			input.add(intval);
		}

		int[] vals = new int[input.size()];

		if (vals.length > 1) {
			vals[0] = input.get(0);
			vals[1] = Math.max(input.get(0), input.get(1));

			for (int i = 2; i < input.size(); i++) {

				tempMax = Math.max(vals[i - 2], vals[i - 2] + input.get(i));

				vals[i] = Math.max(tempMax, input.get(i));
				if (i - 3 >= 0) {

					int tempMax2 = Math.max(vals[i - 3],
							vals[i - 3] + input.get(i));
					vals[i] = Math.max(tempMax2, vals[i]);
				}
			}
		}
		tempMax = -99999999;
		for (int i = 0; i < vals.length; i++) {
			if (vals[i] > tempMax) {
				tempMax = vals[i];
			}
		}
		System.out.println("Maximum sum=" + tempMax);
	}
}

#include<stdio.h>
#define max(x,y) (x>y?x:y)
int findsum(int a[],int n)
{
if(n==0)
return (a[0]>0?a[0]:0);
int i,x,y,z,tem;
x=a[0]>0?a[0]:0;
y=a[1]>0?a[1]:0;
z=0;
for(i=2;i<n;i++)
{
tem=z;
z=x;
x=y;
y=(max(tem,z))+(max(a[i],0));
}
return max(x,y);
}
int main()
{
int a[]={-5,-6,-10,-40,50,-35};
int n=sizeof(a)/sizeof(a[0]);
printf("max sum=%d",findsum(a,n));
return 0;
}

Dynamic programming with Memoization

static int MaxSumBase(int[] input)
        {
            
             Hashtable Sums = new Hashtable();
            int [] memo = new int[input.Length];
            for(int i=0; i< memo.Length;i++)
                memo[i]= int.MinValue;

             for (int i = 0; i < input.Length; i++)
                 Sums.Add(i, MaxSum(input, i, memo));
             return Max(Sums);
        }

        static int MaxSum(int[] input, int index,int []memo)
        {
            if (index >= input.Length)
                return 0;

            if(memo[index] != int.MinValue)
                return memo[index];
            Hashtable Sums = new Hashtable();
            for(int i= index+2; i< input.Length; i++)
                Sums.Add(i,MaxSum(input,i,memo));

            int maxofSums = Max(Sums);
            memo[index] = input[index] + (maxofSums != int.MinValue ? maxofSums : 0);
            return memo[index];
        }

        static int Max(Hashtable sums)
        {
            int max = int.MinValue;
            foreach (int entry in sums.Values)
                if (entry > max)
                    max = entry;
            return max;
        }

int maxSum(int A[],int n)
{
int M[n+1];
M[0]=A[0];
M[1]=A[0]>A[1]?A[0]:A[1];

for(int i=2;i<n;i++)
M[i]=M[i-1]>M[i-2]+A[i]?M[i-1]:M[i-2]+A[i]
return M[n-1];
}

Would you please clarify the task: is the task to find the largest sum of consequent numbers?

I dont know whether this solution is appropriate or not...

if I traverse the array linearly twice, I can find the largest and second largest element respectively in O(n+n) = O(n) time.
Thus we are done with the maximum sum as the largest and second largest element gives the maximum sum.
Now if we introduce the condition while finding the second largest element I think, we are done!

Need comment from all of you!

How about

public int nonContinousMax(int[] array) {
		int maxIncludedPrev = 0;
		int maxExcludedPrev = 0;
		for (int i = 0; i < array.length; i++) {
			if (i == 0) {
				maxIncludedPrev = array[i];
				continue;
			} else {
				if ((maxExcludedPrev + array[i]) > maxExcludedPrev) {
					maxExcludedPrev = maxExcludedPrev + array[i];
					maxIncludedPrev = maxExcludedPrev + maxIncludedPrev;
					maxExcludedPrev = maxIncludedPrev - maxExcludedPrev;
					maxIncludedPrev = maxIncludedPrev - maxExcludedPrev;
				} else {
					maxExcludedPrev=Math.max(maxExcludedPrev, maxIncludedPrev);
					maxIncludedPrev=maxExcludedPrev;
				}
			}
		}
		return Math.max(maxIncludedPrev, maxExcludedPrev);
	}

def maximumSum(arr):
	excl, incl = 0, arr[0]
		
	for i in range(1, len(arr)):
		new_excl = max(incl, excl)
			
	    	incl = excl + arr[i]
	   	excl = new_excl;
	  
	return max(incl, excl)