Leetcode BiWeekly contest 109 - Medium - Visit Array Positions to Maximize Score

In this video we discuss the third problem of Leetcode BiWeekly contest 109

[HimanshuYadav-ppue]

Who Have Still not understood (for you )



we are creating two subsequence sum
and we take nums[i]+((e)end(e is even if nums[i] even )) at point from same sequnce with cost 0
and if we take the sum from opposite subsequence sum to max out sum (nums[i]+(e)end(if nums[i] even then e is odd))then the cost is x

Edge case -


if the first number is even then whenever the first odd will come the parity will be different but we are not monitoring the previous number parity in for loop so for that we are precomputing and substrating x from oddend incase start number is even
and substrating from evenend if the first number is odd

[smitrajrana]

I still have a doubt. I am unable to get the intuition to update oddEnd when nums[0] is even (or vice-versa) as in the for-loop we update either the evenEnd or oddEnd, depending upon the parity of nums[i]. Can you help me?

[mshreeharshabhat]

I am trying another approach.
Starting from the 0th index I check whether the next index is even or odd and depending on prev selected index I compare it with evenSum and oddSum in rest part of the array and decide whether to take that element.

long long maxScore(vector<int>& nums, int x) {
ll evenSum=0;
ll oddSum=0;
int n=nums.size();
for(int i=0;i<n;i++){

else oddSum+=nums[i];
}

else oddSum-=nums[0];

ll points=nums[0];
ll curr=0;
for(int i=1;i<n;i++){
if(nums[curr]%2==0){
if(nums[i]%2==0){
points+=nums[i];
evenSum-=nums[i];
curr=i;
}
else{
ll ifJump=oddSum-x;
if(ifJump>evenSum){
points-=x;
points+=nums[i];
curr=i;
oddSum-=nums[i];
}
else{
oddSum-=nums[i];
}
}
}
else{
if(nums[i]%2==1){
points+=nums[i];
oddSum-=nums[i];
curr=i;
}
else{
ll ifJump=evenSum-x;
if(ifJump>oddSum){
points-=x;
points+=nums[i];
curr=i;
evenSum-=nums[i];
}
else{
evenSum-=nums[i];
}
}
}
}
return points;
}

I don't know why it's failing....

[Vipul_chaudhary_]

Everytime I am not able to solve problems above 2 in contest after spending more than hour.

[durgaprasadvelagapudi]

good explanation. can you let me know what tool you use to draw on the web page. Also what software and device (ipad / mac/ windows)?

looks easy after going through the explanation. getting the intution is the tricky party in a contest/interview.
class Solution {
public long maxScore(int[] nums, int x) {

long[] dp = {-x, -x};
long ans = 0;
if (nums[0] % 2 == 0)
dp[0] = nums[0];
else
dp[1] = nums[0];
//dp[nums[0]&1] = nums[0];
for (int i = 1; i < nums.length; i++){
int curr = nums[i];
if ((curr & 1) == 0){
//even .. update dp[0]
dp[0] = Math.max(dp[0], dp[1] - x) + curr;
} else {
dp[1] = Math.max(dp[1], dp[0] - x) + curr;
}
ans = Math.max(dp[0], dp[1]);
}
return ans;
}
}

[divyanshuagarwal]

i was trying dp got tle i am very sad
class Solution {
public long maxScore(int[] nums, int x) {
long[] dp= new long[nums.length+1];
for(int row= nums.length-1; row>=0; row--){
long take = 0;
long[] temp = new long[nums.length+1];
for(int col= 0; col< nums.length; col++){

take = nums[row]+dp[row];
}else
take = nums[row]+dp[row];
}else{
take = (nums[row]-x)+dp[row];
}
long notake = dp[col];
temp[col] = Math.max(take, notake);
}
dp= temp;
}

return dp[0];
}
}