c programming puzzle

Question

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

I tried it using all possible allowed sums and then finding the maximum (the brute force approach) but is there any better method. Eg for [3 2 7 10] I sum 3,7 and 2,10 and take maximum.

---

More examples:

• [3, 2, 7, 1]: return 10
• [6, 2, 1, 4]: return 10
• [8, 9, 5, 1]: return 13
• [29, 77, 16]: return 77
• [29, 44, 16]: return 45

Answer 1

package com.dan.alg.recursion;

/** * Question: Given an array of positive numbers, find the maximum sum of a subsequence * with the constraint that no 2 numbers in the sequence should be adjacent in the array. * So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 * (sum of 3, 5 and 7).Answer the question in most efficient way. *

* Solution: We will recursively build the solution backwards (starting from the last position * of the array and working our way to the beginning of it) bbased on the following observation: *

* The maximum sum for position p can be obtained from the maximum of the following two values: * V1 = value for position p + maximum sum for position p - 2 (remember, two elements cannot be adjiacent) * V2 = maximum sum for position p - 1 * * @author dan */

public class MaxSumNoNeighbours {

private static int [] arr = { 29, 44, 16 };

/**
 * Determine the max sum for the current position.
 * 
 * @param currentPos    the current position in the array.
 */
private static int maxSum(final int currentPos) {
    //  The sum is zero if we are outside of the bounds.
    if (currentPos < 0) {
        return 0;
    }

    return Math.max(
            arr[currentPos] + maxSum(currentPos - 2), 
            maxSum(currentPos - 1));
}

public static void main (final String [] args) {
    //  Start from the end of the array and work your way forwards
    System.out.println(maxSum(arr.length - 1));
}

}

Answer 2

int choose( int n)
{
   if((n==1) || (n==0))
       return array[n];
   if( n==2)
       return array[0];

   totalSum += max(choose(n-2), choose(n-3));
}

max is a function to get the max no out of the two.

for the ARRAY "array", make function call for each element of the array and store the max result in another array(say arrayOfMax[n])

Answer 3

Python, six lines using dynamic programming (Not really! See edit below.):

def run(x):
    if len(x) == 0:
        return 0
    elif len(x) <= 2:
        return max(x)
    return max(x[0] + run(x[2:]), x[1] + run(x[3:]))

EDIT and Rollback: Although the solution above generates the correct answer, it is not dynamic programming. The one below is, and it uses fewer function calls:

def main(x):
    return max(helper(x))

def helper(x):
    if len(x) == 1:
        return (0, x[0])
    a, b = helper(x[:-1])
    return (max(a, b), x[-1] + a)

Answer 4

F# solution:

let rec maxsubset = function
    | [] -> 0
    | x::[] -> x
    | x::y::xs -> max (maxsubset (y::xs)) (x + maxsubset xs)

Easily adaptable to C-like languages:

using System;
using System.Linq;

namespace Juliet
{
    class Program
    {
        static int MaxSubset(int[] arr, int offset)
        {
            if (offset >= arr.Length)
                return 0;
            else
                return Math.Max(MaxSubset(arr, offset + 1), arr[offset] + MaxSubset(arr, offset + 2));
        }

        static void Test(params int[] nums)
        {
            Console.WriteLine("----------------");
            Console.WriteLine("MaxSubset({0}) = {1}", String.Join(", ", nums), MaxSubset(nums, 0));
        }

        static void Main(string[] args)
        {
            Test(3, 2, 7, 1);
            Test(6, 2, 1, 4);
            Test(8, 9, 5, 1);
            Test(29, 77, 16);
            Test(29, 44, 16);
            Test(239, 2, 3, 111, 1, 4, 546, 4, 3);
            Test(100, 1, 1, 100);
            Console.ReadLine();
        }
    }
}

Answer 5

{

int a[10]={1,2,3,4,5,6,7,89,8,9};

int k=0,i,j,l;
int sum[36],max;

for (i=0;i<10;i++)
{
for (j=i+2;j<10;j++,k++)
sum[k]=a[i]+a[j];
}
max=a[0];
for(i=0;i<36;i++)
printf("sum[%d] is %d\n",i,sum[i]);

for(l=1;l<36;l++)
{
if(max>sum[l])
continue;
else
max=sum[l];
}
printf("%d is the max sum",max);
}

Answer 6

This problem can be solved by dynamic programming.

Let's say we have an array of integers:

i[1], i[2], i[3], ..., i[n], i[n+1], i[n+2]

We partition the array into two parts: the first part containing first n integers, and the second part is the last two integers:

{i[1], i[2], i[3], ..., i[n]}, {i[n+1], i[n+2]}

Let's denote M_SUM(n) as the max sum of the first n integers per your requirement.

There will be two cases:

1. if i[n] is not counted into M_SUM(n), then M_SUM(n+2) = M_SUM(n) + MAX(i[n+1], i[n+2])
2. if i[n] is counted into M_SUM(n), then M_SUM(n+2) = M_SUM(n) + i[n+2]

then, M_SUM(n+2), the value we are seeking for, will be the larger value of the above two.

Then we can have a very naive pseudocode as below:

function M_SUM(n)
   return MAX(M_SUM(n, true), M_SUM(n, false))

function M_SUM(n, flag)
   if n == 0 then return 0
   else if n == 1
      return flag ? i[0] : 0
   } else {
      if flag then
         return MAX(
                M_SUM(n-2, true) + i[n-1], 
                M_SUM(n-2, false) + MAX(i[n-1],i[n-2]))
      else
         return MAX(M_SUM(n-2, false) + i[n-2], M_SUM(n-2, true))
   }

"flag" means "allow using the last integer"

This algorithm has an exponential time complexity.

Dynamical programming techniques can be employed to eliminate the unnecessary recomputation of M_SUM.

Storing each M_SUM(n, flag) into a n*2 matrix. In the recursion part, if such a value does not present in the matrix, compute it. Otherwise, just fetch the value from the matrix. This will reduce the time complexity into linear.

The algorithm will have O(n) time complexity, and O(n) space complexity.

Answer 7

Take for e.g. [3,2,5,10,7]

Solution using dynamic programming:

Maintain two arrays as shown in last two rows

alt text http://img44.imageshack.us/img44/4843/newgp.jpg

The answer will be maximum of two values in the last column (red bold)

Answer 8

Consider the middle element, it may be part of the solution or not. For each case find the best solutions for the left and right remaining sublists and combine these, then pick the better of the two cases.

Answer 9

int findSum(int* arr, int sz)
{
    if( sz <= 0) return 0;

    if( sz == 1)
    {
        return arr[0];
    }
    else
    {
        int a = arr[0] + findSum(arr+2, sz-2); 

        int b = findSum(arr+1, sz-1);

        if( a >= b)
            return a;
        else 
            return b;
    }
}

Answer 10

Cute problem. Easiest approach seems to be to consider the array iteratively, maintaining two best-so-far sums: the best sum you can get when using a[i] is allowed, and the best sum you can get when using a[i] mightn't be allowed. In python:

def best(arr):
    # best sums of zero length array are 0
    ok, bad = 0,0 

    for x in arr:
        # best sum if we can use x is to use it,
        # because all elements are positive
        ok += x

        # moving along one step means we can't
        # use the ok sum, and can use the bad sum
        bad, ok = ok, bad

        # but just because we could use ok, doesn't
        # mean we have to, so if it's better, use
        # that path
        if bad < ok:
            bad = ok

    # bad is then our best possible sum
    return bad

Answer 11

sum[0] = 0;
sum[1] = 0;

for(i = 0; i < arraylength; i++) 
    sum[i & 1] += array[i];

printf("sum = %u\n", MAX(sum[0], sum[1]));
printf("homework completed\n");