CODEWITHSUNDEEP
arraysalgorithmdata-structures
Subhadeep
Subhadeep

Reputation: 257

Maximum sum such that no two elements are adjacent

Now the available solution every where is to have an include and exclude sum . At the end max of these two will give me the output.

Now initially I was having difficulty to understand this algorithm and I thought why not going in a simple way.

Algo: Loop over the array by increasing array pointer two at a time

  1. Calculate the odd positioned element sum in the array
  2. Calculate the even positioned element sum

At the end, take max of this two sum.

in that way, I think complexity will be reduced to half O(n/2)

Is this algo correct?

Upvotes: 5

Views: 4818

Answers (2)

Abhi
Abhi

Reputation: 11

dynamic programming inclusion exclusion approach is correct your algorithm would not work for test cases like 3 2 7 10 in this test case the two elements we take are 3 10 and sum is 13 instead of 3,7 or 2,10.may you understand what i am saying and for further clarity code is below

Java Implementation

public int maxSum(int arr[]) {   // array must contain +ve elements only
 int excl = 0;
 int incl = arr[0];
 for (int i = 1; i < arr.length; i++) {
   int temp = incl;
   incl = Math.max(excl + arr[i], incl);
   excl = temp;
 }
 return incl;
}

Upvotes: 0

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

It's a case of dynamic programming. The algorithm is:

  1. Do not take (sum up) any non-positive items
  2. For positive numbers, split the problem in two: try taking and skiping the item and return the maximum of these choices:

Let's show the 2nd step, imagine we are given:

[1, 2, 3, 4, 5, 6, 10, 125, -8, 9]

1 is positive, that's why 

take_sum = max(1 + max_sum([3, 4, 5, 6, 10, 125, -8, 9])) // we take "1"
skip_sum = max_sum([2, 3, 4, 5, 6, 10, 125, -8, 9])       // we skip "1" 
max_sum =  max(take_sum, skip_sum)

C# implementation (the simplest code in order to show the naked idea, no further optimization):

private static int BestSum(int[] array, int index) {
  if (index >= array.Length)
    return 0;

  if (array[index] <= 0)
    return BestSum(array, index + 1);

  int take = array[index] + BestSum(array, index + 2);
  int skip = BestSum(array, index + 1);

  return Math.Max(take, skip);
}

private static int BestSum(int[] array) {
  return BestSum(array, 0);
}

Test:

Console.WriteLine(BestSum(new int[] { 1, -2, -3, 100 }));
Console.WriteLine(BestSum(new int[] { 100, 8, 10, 20, 7 }))

Outcome:

101        
120

Please, check, that your initial algorithm returns 98 and 117 which are suboptimal sums.

Edit: In real life you may want to add some optimization, e.g. memoization and special cases tests:

private static Dictionary<int, int> s_Memo = new Dictionary<int, int>();

private static int BestSum(int[] array, int index) {
  if (index >= array.Length)
    return 0;

  int result;

  if (s_Memo.TryGetValue(index, out result)) // <- Memoization
    return result;

  if (array[index] <= 0) 
    return BestSum(array, index + 1);

  // Always take, when the last item to choose or when followed by non-positive item
  if (index >= array.Length - 1 || array[index + 1] <= 0) {
    result = array[index] + BestSum(array, index + 2);
  }
  else {
    int take = array[index] + BestSum(array, index + 2);
    int skip = BestSum(array, index + 1);

    result = Math.Max(take, skip);
  }

  s_Memo.Add(index, result); // <- Memoization

  return result;
}

private static int BestSum(int[] array) {
  s_Memo.Clear();

  return BestSum(array, 0);
}

Test:

  using System.Linq;

  ...

  Random gen = new Random(0); // 0 - random, by repeatable (to reproduce the same result)

  int[] test = Enumerable
    .Range(1, 10000)
    .Select(i => gen.Next(100))
    .ToArray();

  int evenSum = test.Where((v, i) => i % 2 == 0).Sum();
  int oddSum = test.Where((v, i) => i % 2 != 0).Sum();
  int suboptimalSum = Math.Max(evenSum, oddSum); // <- Your initial algorithm
  int result = BestSum(test);

  Console.WriteLine(
    $"odd: {oddSum} even: {evenSum} suboptimal: {suboptimalSum} actual: {result}");

Outcome:

  odd: 246117 even: 247137 suboptimal: 247137 actual: 290856

Upvotes: 3

Related Questions