[InterviewBit] Coins in a Line

Coins in a Line

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>

int dp[505][505];
int helper(vector<int>& A, int l, int r) {
if(dp[l][r] != -1) return dp[l][r];
if(l == r) return dp[l][r] = A[l];
return dp[l][r] = max(A[l] - helper(A,l+1,r), A[r] - helper(A,l,r-1));
}
int Solution::maxcoin(vector<int> &A) {
memset(dp,-1,sizeof dp);
int gap = helper(A,0,A.size() - 1), sum = accumulate(begin(A), end(A), 0);
return (sum - gap) / 2 + gap;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/10/07/PS/interviewbit/coins-in-a-line/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.