Well, this is an interesting question and deals with a new (for us) and interesting concept. Have a try..
Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.
Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format
The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes
In all cases, N ≤ 100,000.
Output format
Your output should be a single line consisting of one integer, the maximum number of chocolates that Nikhil can collect.
Sample Input
10
30 10 8 20 11 12 25 13 20 19
Sample Output
95
You can post your solution/logic/hints as a comment.
we can proceed by storing the maximum number of chocolates one can have at position i in an array of size N….then v can find the maximum in that array
this can be done by,
first accept the no. of chocolates in each basket in array v[]
then for i=0 to n
m[i]=v[i] + max(i-2)
at the end return max of all values in array m[]
here max is a function that returns maximum of array m[] from index 0 to i-2 (not i-1 as then it will become consecutive)
Interesting question. Has this been taken from the online programming olympiad thing?
~AA
aman your thing would be rather incomplete right? cause, yours takes in every alternate lpcation of the array, but what if, like in the example, you have to take every third or maybe a third then a second?
The solution is correct if it had the condition been n<=1000 but the program wont work for n=100000
Aman, your solution is an order n*n method so the time & other constraints wont permit it
What i want you is to think more innovatively and to reduce the amount of work the CPU has to do.
Develop on the method you have provided. Its very close to the ideal solution.
im pretty close to getting the answer. basically what im doing is first sorting them and then manipulating them. i have used a made-up method to ensure that they are not next to each other and that is what has a couple of small flaws in it.
I don’t think you’ll be able to get the answer this way.
i dunt think i got ur question rishab…i m storin the max value for every location from 0 to n-1
sajal bhaiyya, instead of using a function max, we can have an array max[] of size n in which the maximum value from 0 to i in array m[] can be stored…..whenever we get a new value in m[], max[] can be easily updated
in short,
max[o]=val[0]
if (val[1]>val[0])
max[1]=val[1]
else
max[1]=val[0]
now,
for i=2 to n
m[i]=val[i] + max[i-2]
if (m[i]>max[i-1])
max[i]=m[i]
else
max[i]=max[i-1]
in the end print max[n]
Yes, thats perfect!
The trick is to use, what we call, DYNAMIC PROGRAMMING (DP).
The way to approach the problem is as follows
Consider a subsequence of numbers initially (basically subproblems), viz.,
Step 1
We just have 30
So the best possible is 30 (call it step1_max)
Step 2
We have 30 & 10
So the best possible is still 30(step2_max)
Step 3
We have 30 , 10 , 8
So the best possible is (8+step1_max) OR step2_max
Compare and store the answer as step3_max (here its 30+8=38)
Step 4
we have 30, 10 ,8, 20
20+step2_max or step_3 max
=step4_max=50
We proceed further in the similar manner
For the algorithm you can have a look at Aman's comment.
I will post a little more about dynamic programming soon.
So the final code is this:
#include
#include
using namespace std;
int max(int x,int y)
{
if (x>y)
{return x;}
else
{return y;}
}
int main()
{
int a[100000],s[100000],n=0,ans=0;
cin>>n;
for (int init=0;init<100000;init++){
a[init]=0;
s[init]=0;
}
for (int num=0;num>a[num];
}
s[0]=a[0];
s[1]=max(a[0],a[1]);
for (num=2;num