Maximum sum such that no two elements are adjacent

Given an array, find the maximum sum of a subsequence with the constraint that no two 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).

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication2

{

    class Program

    {

        static void Main(string[] args)

        {

            //Maximum sum such that no two elements are adjacent

            int[] numArray = { 3, 2, 5, 10, 7 };

            int maxSum = 0;

            for (int i = 1; i <= numArray.Length; i++) //window length

            {

                for (int j = 0; j <= numArray.Length – i; j++) //starting position

                {

                    for (int p = 2; p <= j + i + 1; p++) //increment loop counter

                    {

                        int tempSum = 0;

                        for (int k = j; k < j + i; k = k + p)

                        {

                            tempSum = tempSum + numArray[k];

                        }

                        if (i == 1 && j == 0 && p == 2)

                        {

                            maxSum = tempSum;

                        }

                        else if (tempSum > maxSum)

                        {

                            maxSum = tempSum;

                        }

                    }

                }

            }

            Console.WriteLine("Max Sum = " + maxSum);

        }

    }

}

Max Sum = 15
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s