can someone provide the solution of swapping question
Use this dp approach:
rl=dp[i2]+ a[i1].i + a[i].(i+1);
lr=dp[i2]+ a[i].i + a[i1].(i+1);
pf=dp[i1]+ a[i].(i+1);
ll m=max1(rl,lr,pf);
dp[i]=m;
Did see you participating in lunchtime ?
sir can u explain little bit more??
Thanksâ€¦
Yes, sir sureâ€¦Iâ€™ll explain few minutesâ€¦
Standard DP problem  bottom up approach. For each element at index i you can either skip swapping it or swap it with itâ€™s adjacent element i + 1.
The answer is thus maximum of the two, i.e. dp[i] = max(dp[i+1], dp[i+2])
with the base case dp[n1] = arr[n1].
Recursive solution: https://www.codechef.com/viewsolution/25450383
Might be easier to understandâ€¦
Works fine even without lr
What I did wasnâ€™t provocatively a DP solution but rather very intuitive.
1.>First find the sum of the array with sum+=a[i]*(i+1).
2.>second make an array with the difference of elements of a like b[i]=a[i]a[i+1];
3.>now you have an array with the prefix differenceâ€¦ to maximise the sum, you have to take all
positive difference and in such a way that no two difference are adjacent
for example lets say a[]={5,3,2,4,1} so our difference array will be {2,1,2,3}. So now we will have
to take the maximum possible subsequence such that its sum is maximum from the diff
arrayâ€¦ so itâ€™ll be 2+3; so we have our val=5 , and so iâ€™ll update it accordingly like:
maxm=max(sum,sum+val); => sum=38 and val =5 so ans=43.
4.>So now, How to take maximum sum subsequence such that no two elements of that are
adjacent? Well itâ€™s a pretty conventional approach , You can either maintain an array dp[] and
take maximum including and excluding the element or just traverse through the array
calculating the sameâ€¦
Hereâ€™s my submission if you want to take a look: [https://www.codechef.com/viewsolution/25460118]
lol PKMKB sahi hain
can some one explain easy dp solution for this problem more elaborately.
Anyways nice approach
here say you have 3 elements you have 2 choices 1) swap a1 and a2 ; 2)swap a2 and a3
so using dp solve for first 3 elements and then recursively call the function.
https://www.codechef.com/viewsolution/25456156
here initially calculate (i)*a[i] for the input array and in every swap you basically gain the difference of the 2 elements being swapped , g[i] stores then gain for the last n elements add the gain for the whole array to sum(i*a[i]) and you get the answer.
This is a classic case of â€śBottoms Upâ€ť.

Imagine a test case with just one element. For this the optimal approach is â€śNo SWAPâ€ť. The final answer is the same as input. This will be DP[0].

Now, imagine two inputs. Consider the following two values:
 The second input multiplied by 2 + first multiplied by 1 = x
 The first input multiplied by 2 + second multiplied by 1 = y
if x is larger than y, it means no swap was needed and final answer is 2A2 + 1A1. Or else now the output will be 2A1+1A2. This will be DP[1].
 Now lets analyze the third case, with three elements. Here  we have two â€śpossibilitiesâ€ť. We could swap 3rd input and 2nd input; or we need not. If have to swap 3rd input and 2nd input, then we cannot swap 2nd and 1st input. That is the cost we pay. But DP[1] took into account the benefit of swapping 1st and 2nd element! Thus DP[1] is, so to say, "corrupted. DP[0] talked about the best case before 1st and 2nd element were swapped.
So we have to compare DP[0]+swap_benefit vs DP[1]+no_swap_of_3_2. Whichever is better becomes our DP[2]. Here swap_benefit means benefit of swapping (3,2) over (2,1).
Generalizing, for DP[k]  we need to analyze:
DP[k] = MAX(DP[k2]+swap, DP[k1]+no_swap).
Hey @tanha_barati even i too did the same thing, Once i got the difference array, i traversed on it and on getting a positive number i stored it, and on getting a negative or a zero value, i took my stored vector and found the highest sum giving subsequence in it, and added it to the the answer.
I choose the highest sum giving subsequence in the following manner.
suppose we have v = {2,3,4,5,6};
as we have only positive numbers we only have two choices, summing up the odd indexed values and summing the even indexed values and then find their maximum, that will be the maximum sum.
But i got WA for my this approach, i have tried my code with numerous test cases and it seems to be giving same anwer as the other correct ones, please tell me what is wrong with my this approach.
dp[0]=0;
dp[1]=a[1];
for(int i=2;i<=n;i++)
{
dp[i] = max(a[i]*i + dp[i1], dp[i2] + a[i]*(i1) + a[i1]*i);
}
return dp[n];
Solution Approach: Think Dynamically as statement said in the problem::
 Keep element at its own place i.e, result till previous index + a[i] * i;
 Swap the recent two element. ie. result till i2 index + a[i] * (i1) + a[i1] * (i);
Store the maximum of the two.