Maximum sum of non adjacent subsequence sum

Problem

Finding the maximum subsequence sum such that non of the elements in the sequence are adjacent to each other

Approach

One brute force approach is getting all the combinations, and excluding any combination with adjacent elements and finding the maximum from the remaining combinations. Obviously the approach is exponential. Below is the solution to solve the problem using Dynamic Programming.

In-order to solve a problem using dynamic programming there should be a solution which has optimal substructure and overlapping sub problems properties. And the current problem has optimal substructure property.

Say, f( i) is defined as maximum subsequence sum of non adjacent elements for 'i' items, then

then

f( i) =     0 if i = 0

               max (f(i-1), f(i-2) + a[i])

Below is the algorithm for the same (note it can solved without the encapsulating data in 'record' - i just preferred it this way) - which should illustrate the above idea:

Code Snippet

30. int FindMaxNonAdjuscentSubsequentSum(int[] a)
31.         {
32.             a.ThrowIfNull("a");
33.             if(a.Length == 0)
34.             {
35.                 return 0;
36.             }
37.             Record r = new Record()
38.             {
39.                 max_including_item = a[0],
40.                 max_excluding_item = 0
41.             };
42.             for (int i = 1; i < a.Length; i++)
43.             {
44.                 var t = new Record();
45.                 //there will be only two cases
46.                 //1. if it includes the current item, max is maximum of non adjuscent sub
47.                 //sequence sum so far, excluding the last item
48.                 t.max_including_item = r.max_excluding_item + a[i];
49.                 //2. if it excludes current item, max is maximum of non adjuscent subsequence sum
50.                 t.max_excluding_item = r.Max;
51.                 r = t;
52.             }
53.             return r.Max;
54.         }

Unit Tests

Code Snippet

55. [TestMethod]
56.         [TestCategory(Constants.DynamicProgramming)]
57.         public void MaxNonAdjascentSubsequenceSum()
58.         {
59.             int[] a = new int[] { 3, 2, 5, 10, 7};
60.             Assert.IsTrue(15 == this.FindMaxNonAdjuscentSubsequentSum(a));
61.             a = new int[] { 3, 2, 5, 10 };
62.             Assert.IsTrue(13 == this.FindMaxNonAdjuscentSubsequentSum(a));
63.             a = new int[] { 5, 10, 40, 50, 35 };
64.             Assert.IsTrue(80 == this.FindMaxNonAdjuscentSubsequentSum(a));
65.             a = new int[] { 1, -1, 6, -4, 2, 2 };
66.             Assert.IsTrue(9 == this.FindMaxNonAdjuscentSubsequentSum(a));
67.             a = new int[] { 1, 6, 10, 14, -5, -1, 2, -1, 3 };
68.             Assert.IsTrue(25 == this.FindMaxNonAdjuscentSubsequentSum(a));
69.         }

Helpers

Code Snippet

14. public static int Max(int a, int b)
15. {
16. return (a > b) ? a : b;
17. }
18. class Record
19. {
20. public int max_including_item = int.MinValue;
21. public int max_excluding_item = int.MinValue;
22. public int Max
23. {
24. get
25. {
26. return Max(max_including_item, max_excluding_item);
27. }
28. }
29. }