for programming interview-part7

today we shall discuss a problem related to finding max sum in array such that max sum elements are not adjacent to each other.ie if the array element are given as
1,3,5,10=>13
1,7,9,21=>22
ans

#include < iostream >
using namespace std;
void FindMaxSum(int buf[],int cnt)
{
int incl = 0; // max sequence including the previous item
int excl = 0; // max sequence excluding the previous item
int excl_new=0;

for (int i = 0; i < cnt; i++)
{
// current max excluding i
if (incl > excl)
{excl_new = incl;
cout << "if\t" << excl_new << endl;
}
else
{
excl_new = excl;
cout << "else\t" << excl_new << endl;
}

// current max including i
incl = excl + buf[i];
excl = excl_new;


}
cout << "\nmax sum = " << ((incl > excl)? incl : excl) << endl;
}
int main()
{
int a[5]={3,2,7,10};
FindMaxSum(a,5);
getchar();
return 0;
}

we shall discuss another beautiful problem which is one of my all time favorites the knapsack problem.hope all of u would have studied about this in CLRS.

let W be max weight
let A[] be the array with articles of different weights.
let n be the max number of items

int findprice(int A[],int n)
{
int cost=0;
for(int i=0;i < n;++i)
cost+=max(findprice(A[],n-1),A[i]+findprice(W-A[i],n-1));
return cost;
}

here we can bring various optimization like using dynamic programming like storing in table the values instead of using subsequent rec call

for programming interviews part 7

hi today we shall discuss the problem related to arrays
12.how to left roate an array
#include < iostream >
int main()
{
using namespace std;
int a[5]={3,4,5,1,2};
int k=5,temp=0,i;
for(i=k;i < 5 ;++i)
{

temp=a[i];
a[i]=a[i-k];
a[i-k]=temp;
}
for(i=0;i < 5;++i)
cout << a[i] << endl;
cin.sync();
cin.get();
return 0;
}
14.how to find element in sorted array which is rotated in O(logn)

#include < iostream >
int main()
{
using namespace std;
int a[5]={2,3,4,5,1};
int mid=0,l=0,r=4,key=5;
while(l<=r)
{
mid=l+(r-l)/2;
if(a[mid]==key)
{
cout << mid;
break;
}
if(a[l] > a[mid])
{
if((key > a[mid])&&(key < a[l]))
l=mid+1;
else
r=mid-1;
}
else if(a[r] < a[mid])
{
if((key > a[r])&&( key < a[mid]))
r=mid-1;
else
l=mid+1;
}
else if(key < a[mid])
r=mid-1;
else
l=mid+1;
}



cin.sync();
cin.get();
return 0;
}

16.how to find product of elements in arrray for ith element the product shlould be all the element except ith element without using / operator

#include < iostream >
int main()
{
using namespace std;
int arr[5]={1,2,3,4,5};
int i=0,l=1,r=1;
int res[5]={1,1,1,1,1};
for(i=0;i < 5;++i)
{
res[i]*=l;
res[4-i]*=r;
l*=arr[i];
r*=arr[4-i];
}
for(i=0;i<5;++i)
cout << res[i] << endl;
cin.sync();
cin.get();
return 0;
}