CODEWITHSUNDEEP
algorithm
dmonopoly
dmonopoly

Reputation: 3331

How to find the algorithm: given an array of integers, what is the maximum sum of a subset of the integers such that

Given an array of integers, what is the maximum sum of a subset of the integers such that the integers in the subset were not originally next to each other?

Examples:

[3, 8, 4] => max sum is 8, since 8 > (3+4)
[12, 8, 9, 10] => max sum is 12 + 10 = 22, since this is greater than 12 + 9 and 8 + 10

I'm interested in figuring out the algorithm for doing this. Methodology / thinking process = greatly appreciated.

EDIT: The integers range from 1 to 1000, inclusive. (Since this is entirely a learning exercise, I'd still be interested in learning about different methods if the integers ranged from, say, -1000 to 1000.)

Upvotes: 1

Views: 4722

Answers (4)

Ivan Bianko
Ivan Bianko

Reputation: 1769

Let you have array A {Ai, 1 <= i <= n }

F(i) - Maximum sum of subarray Aj { 1 <= j <= i }, then

F(0) = 0 - empty subarray

F(1) = A(1) - only first element

F(i) = max(F(i-2) + A(i), F(i-1)) , 2 <= i <= n

F(n) - answer

C++ implementation:

int GetMaximumSubarraySum(const vector<int>& a)
{
    // note that vector a have 1-based index
    vector<int> v(a.size());
    v[0] = 0;
    v[1] = a[1];
    for(int i =2; i < a.size(); i++)
        v[i] = max(v[i-2] + a[i], v[i-1]);

    return v.back();
}

Explanation:

First, main idea is to use dynamic programming. We try to solve task for array with N element by using known answer for array with N-1 and N-2 first elements. If N = 0 the answer is 0 and if N = 1 the answer is A[1]. It's clear. For N >= 2 we have 2 different ways:

  1. Use element A[N], then the answer is A[N] + F[N-2] (because we can't use A[N-1] element and F[N-2] is the best solution for subarray 1..N-2, we don't care about if F[N-2] element is used or not, this is just the best solution for subarray 1..N-2.

  2. Don't use element A[N], then the answer is F[N-1] (because we can use A[N-1] element and F[N-1] is the best solution for subarray 1..N-1, also we don't care about if F[N-1] element is used or not.

So we need to get max of this 2 situations. To solve the task you need calculate F[N] in increasing order and memorize answers.

Let see at your example:

[12, 8, 9, 10]

F[0] = 0

F[1] = 12 - use 1-st element

F[2] = max(F[0]+A[2], F[1]) = max(8, 12) = 12 - use 1-st element

F[3] = max(F[1]+A[3], F[2]) = max(21, 12) = 21 - use 1-st, 3-rd element

F[4] = max(F[2]+A[4], F[3]) = max(22, 21) = 22 - use 1-st, 4-th element

The answer is F[4] = 22.

Upvotes: 9

mcdowella
mcdowella

Reputation: 19621

The only uniformly successful thinking process I know is to have seen the problem before. Looking at your question my first thought was "I need to maximise a sum subject to what seems to be a set of fairly simple boolean constraints". In Knuth Vol 4A section 7.1.4 Algorithm B Knuth describes how to solve such a problem, as long as the constraints can be expressed as a http://en.wikipedia.org/wiki/Binary_decision_diagram of manageable size. If you already have a BDD package, you can therefore solve a whole class of problems of this type just by constructing a BDD that describes your particular constraints.

My second thought was to note that later on in the same section, Knuth shows connections between BDDs and linear networks of boolean logic. Given this, there should be a tractable dynamic programming solution to your problem. If you are looking for a general methodology to learn, dynamic programming is a pretty good candidate. In this case it seems to lead to an algorithm pretty much like that presented by Ivan Benko, although he seems to be working under the assumption - supported by your example data - that the integers are all >= 0, and it could work for general integers with a few more if statements.

Upvotes: 2

Fopa L&#233;on Constantin
Fopa L&#233;on Constantin

Reputation: 12373

Here is a solution know as the kadane's Alogithme

Algorithm 1 Kadane’s algorithm
   M ← 0, t ← 0
   i ← 1
   for j ← 1 to n do          
      t ← t + a[j]
      if t > M then M ← t, (x1 , x2 ) ← (i, j)           
      if t ≤ 0 then t ← 0, i ← j + 1// reset the accumulation
   end for
   output M , (x1 , x2 )

Upvotes: 0

MBo
MBo

Reputation: 80287

Think recursively: Best result is maximum from cases- to use first element (first in recursion branch) or not to use it in sum

Best(i) = Max(A[i] + Best(i + 2), Best(i + 1))

Upvotes: 0

Related Questions