Maximum sum such that no two elements are adjacent - GeeksforGeeks

Maximum sum such that no two elements are adjacent - GeeksforGeeks
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.

Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

includeSum[k] = excludeSum[k-1] + data[i]
excludeSum[k] = Max(includeSum[k-1], excludeSum[k-1])

That said, we don't need to keep an array of previous maximum sums. All we need are just previous includeSum and excludeSum.

http://www.fgdsb.com/2015/01/03/find-max-values/

跟栅栏上色问题是一样的，只关心上一个和上上一个记录，所以不需要O(n)的space，O(1)足矣。
这题还有这样一种表达：
有一溜n个房子，每个房子里面的东西的value是给定的一个正整数，小偷准备去偷东西来maximize gain，但是有一个条件是不能偷连续两幢房子的东西，因为房主挨偷以后会告诉左右邻居。要求给出能偷到的最大value的值。

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);

}

http://tech-queries.blogspot.com/2009/05/max-possible-sum-of-non-consecutive.html

 If we denote the ith element as T(i) and max sum till ith element of the array as S(i), then

S(i) = MAX {S(i-1), S(i-2) + T(i) }
S(-1) = 0;
if i=0, S(i) = T(0);

int max_value(const vector<int>& nums) {

if(nums.empty()) return 0;

int prev_prev = 0, prev = nums[0];   

for(int i = 1; i < nums.size(); ++i) {

int old_prev = prev;

prev = max(prev, max(nums[i] + prev_prev, prev));

prev_prev = old_prev;

}   

return prev;

}

O(n^2) time and O(n) spaces:
http://n00tc0d3r.blogspot.com/2013/07/maximum-sum-of-non-contiguous.html
One way to improve is to use backtracking: Store the known maxSum for subarrays we have visited, [0 .. k]. More specifically,

maxSum[k] = maximum sum of subsequences of array [0 .. k] that include array[k].

Now the algorithm becomes:

• For each element in the array, find the maximum sum of array[k]+maxSum[j] where 0 <= j < k-1.
  Notice that maxSum[k-1] includes array[k-1] and thus it cannot include array[k].

 public int maxSumInSubsequence(int[] data) {  
   if (data == null) return 0;  
   int n = data.length;  
   
   // maxSum[i] == the maximum sum of subsequences of data[0 .. i] that include data[i]  
   int[] maxSum = new int[n];  
   for (int i=0; i<n; ++i) {  
     maxSum[i] = data[i];  
     // maxSum[i-1] includes data[i-1] and thus cannot include data[i]  
     for (int j=0; j<i-1; ++j) {  
       maxSum[i] = Math.max(data[i] + maxSum[j], maxSum[i]);  
     }  
   }  
   
   // find the max of all subsequences  
   int max = 0;  
   for (int i=0; i<n; ++i) {  
     max = Math.max(max, maxSum[i]);  
   }  
   
   return max;  
 } 

Extension:
Max non-contiguous sum with loop
TopCoder Dynamic Programming Bad Neighbours Donation Collection Problem
http://justprogrammng.blogspot.com/2015/02/topcoder-dynamic-programming-bad.html
http://www.krishnabharadwaj.info/dynamic-programming/
Same as Leetcode House Rubber II: http://massivealgorithms.blogspot.com/2015/05/leetcode-213-house-robber-ii-csdnnet.html
Read full article from Maximum sum such that no two elements are adjacent - GeeksforGeeks