CareerCup

int FindMaxSum(int arr[], int n)
{
  int incl = arr[0]; 
  int excl = 0;      
  int excl_new;
  int i;
  
  for (i = 1; i < n; i++)
  {
     /* current max excluding i */
     excl_new = (incl > excl)? incl: excl;
 
     /* current max including i */
     incl = excl + arr[i];
     excl = excl_new;
  }
 
   /* return max of incl and excl */
   return ((incl > excl)? incl : excl);
}

Works flawlessly:

int findMax(int[] A){
		int max[] = new int[A.length];

		//Initialization Code
		if (A.length >= 2){
			max[0] = A[0] > 0 ? A[0] : 0 ;
			max[1] = A[1] > 0 ? A[1] : 0 ;
		}
		else{
			if (A.length > 1){
				return (A[0] > A [1]) ? A[0] : A[1];				
			}
			else
				return A[0];
		}
		boolean posFlag = false;
		//Dynamic programming to calculate max-sum sub-array 
		for (int i = 2; i< A.length; i++){
			int num = 0;
			
			if (A[i] > 0){
				num = A[i];
				posFlag = true; //to check if there was at least 1 positive number
			}
			max[i] = num + getMax(max,0,i-2);
		}
		//If all numbers were negative, the highest number is the max sum
		if (!posFlag) return getMax(A,0,A.length-1);

		//Else return the maximum
		return getMax(max, 0, max.length-1);
	}

	int getMax(int[] A, int p, int r){
		int max = A[p];
		for(int i = p+1; i<= r; i++){
			if (A[i] > max)
				max = A[i];
		}
		return max;
	}

maxsum[1...i] = max(maxsum[1...i-1] , maxsum[1...i-2] + a[i])

is the given array sorted?
define "adjacency"... in the array 1 3 2 4 5, are 2 and 3 adjacent or 3 and 4 in the conventional sense?

You want to know solution for maximum sum subsequence problem ?

Array is not sorted and sorting is not allowed

If the numbers are all positive then will it not be the entire array.

You can also find some good discussion here. web.media.mit.edu/~dlanman/courses/cs157/HW4.pdf

import java.util.Arrays;



public class ArraysSum {

public void arraySum(int[] arr){
int arraySize=arr.length;
int[] tmparr=new int[arraySize];
System.arraycopy(arr,0,tmparr,0, arr.length);
Arrays.sort(tmparr);
// getting another array with the sorted positions list
for(int i=arraySize-1;i>=0;i--){
int search=tmparr[i];
for(int j=0;j<arraySize;j++){
if(arr[j]==search){ tmparr[i]=j;break;}
}
}
System.out.println("Sortedpositions - array");
for(int j=0;j<arraySize;j++)
System.out.println(tmparr[j]+"-"+arr[j]);
//calculating the sum depending on the positions in tmparr array
int sum=arr[tmparr[arraySize-1]],prevPos=tmparr[arraySize-1];
System.out.println(sum);
for(int i=arraySize-2;i>=0;i--)
{
if(tmparr[i]!=prevPos+1 && tmparr[i]!=prevPos-1)
{
sum+=arr[tmparr[i]];
prevPos=tmparr[i];
}

}
System.out.println(sum);
}

public static void main(String args[]){
ArraysSum as=new ArraysSum();
int[] arr={1,4,3,5,9,23,2};
as.arraySum(arr);
}

}

#include<iostream>
using namespace std;
int maxsum(int a[],int n)//using Dynamic Programming
    {
        int lis[n];
        for(int i =0;i<n;i++)
        {
            lis[i] = a[i];
        }
        for(int i =1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(j != i-1)
                {
                    if(lis[i] < lis[j] + a[i])
                    {
                        lis[i] = lis[j] + a[i];
                    }
                }    
            }
        }
        int max = lis[0];
        for(int i =1;i<n;i++)
        {
            if(lis[i] > max)
            {
                max = lis[i];   
            }   
        }
        return max;
    }

int maxSum(int *a, int n)
{
if(n<=0)
return 0;
if(n == 1)
return a[0];
if(n == 2)
return (a[0]>a[1]?a[0]:a[1])
else
{
return max(maxSum(a,n-2) + a[n-1], maxSum(a,n-1));
}
}

nice and simple

nice and simple