Блог пользователя Nishu_Coder

Автор Nishu_Coder, история, 11 месяцев назад, По-английски

Problem link: https://leetcode.com/problems/visit-array-positions-to-maximize-score/ Doubt: I tried with recursive dp but only 711/744 testcases passed. My code:

class Solution { public:

long long fun (int index,int r,long long score2,vector<int>&nums,int n,vector<long long>&dp)
{

    if(index == n)
    {
        return 0;
    }

    if(dp[index]!=-1e12)
    {
        return dp[index];
    }

    long long y = score2;
    long long start_score = score2;

    for(int i = index + 1;i<n;i++)
    {
        long long temp1 = score2 + fun(i,r,nums[i],nums,n,dp);
        if((nums[i]%2LL)!=(nums[index]%2LL))
        {
            temp1-=r;
        }
        start_score = max(start_score,temp1);
    }

  dp[index] = start_score;
   return dp[index];

}


long long maxScore(vector<int>& nums, int x) 
{
    int n = nums.size();
    vector<int>temp;
    temp.push_back(0);

    vector<long long>dp(n);
    for(int i = 0;i<n;i++)
    {
        dp[i] = -1e12;
    }


   return fun(0,x,nums[0],nums,n,dp);


 //return dp[0];

}

};

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Nishu_Coder (previous revision, new revision, compare).