Maximum Sum Such that No Two Elements are Adjacent

Question: Given an array all of whose elements are 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.
Ex-1:  3 2 7 10 should return 13 (sum of 3 and 10) .
Ex-2: 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Algorithm:

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

At the end of the loop return max of incl and excl.

Explanation:

  arr[] = {5,  5, 10, 40, 50, 35}

  inc = 5
  exc = 0

  For i = 1 (current element is 5)
  incl =  (excl + arr[i])  = 5
  excl =  max(5, 0) = 5

  For i = 2 (current element is 10)
  incl =  (excl + arr[i]) = 15
  excl =  max(5, 5) = 5

  For i = 3 (current element is 40)
  incl = (excl + arr[i]) = 45
  excl = max(5, 15) = 15

  For i = 4 (current element is 50)
  incl = (excl + arr[i]) = 65
  excl =  max(45, 15) = 45

  For i = 5 (current element is 35)
  incl =  (excl + arr[i]) = 80
  excl = max(5, 15) = 65

And 35 is the last element. So, answer is max(incl, excl) =  80.

C++ Code:

    #include <iostream>

    using namespace std;
     
    int FindMax(int a[],int l){
        int incl=a[0];
        int excl=0;

        for(int i=1;i<l;i++){
            int excl_new=(incl>excl)?incl:excl;
            incl=excl+a[i];
            excl=excl_new;
        }

        return (incl>excl)?incl:excl;
    }
     
    int main(){
        int a[]={3,2,7,10};
        cout<<FindMax(a,4)<<endl;
    }

Converting Decimal to Hexa-Decimal

In this blog i will be writing all crap code for the questions asked in various interviews.

Starting with the following question.

How to convert a decimal number to its equivalent Hexa-decimal equivalent. Give a C/C++ code for the same.

Explanation and Algorithm :

If you don't know or Forgotten what is Decimal/Hex-Decimal Numbers, the following table will tell u that.

HEXADECIMAL	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
DECIMAL	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Steps:

1. Divide the decimal number by 16.   Treat the division as an integer division. 
2. Write down the remainder (in hexadecimal).
3. Divide the result again by 16.  Treat the division as an integer division. 
4. Repeat step 2 and 3 until result is 0.
5. The hex value is the digit sequence of the remainders from the last to first.

Example: Convert the number 188 DECIMAL to HEXADECIMAL

DIVISION	RESULT	REMAINDER (in HEX)
188 / 16	11	C (12 decimal)
11 / 16	0	B (11 decimal)
ANSWER		BC

C++ Code:

#include <iostream>

using namespace std;

int main(){
    int iDecimalNumber;
    cout<<"Enter a decimal number to convert it to Hex :";
    cin>>iDecimalNumber;
    cout<<"Its Hex Equivalent is: "<<hex<<iDecimalNumber<<endl;
}

C Code:

#include "stdio.h"

int main(){
    int iDecimalNumber;
    printf("Enter a decimal number to convert it to Hex :");
    scanf("%d",&amp;iDecimalNumber);
    printf("Equivalent Hexa-Decimal Number is :");
    printf("%X\n",iDecimalNumber);
}

Simple isn't it :P. you didn't like it ??.
You can go around the globe. Think smart :D.