nikunjsoni

1406

Jul 26th, 2021
134
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     string stoneGameIII(vector<int>& A) {
  4.         int n = A.size();
  5.         vector<int> dp(n, -1e9);
  6.         for (int i = n - 1; i >= 0; --i) {
  7.             for (int k = 0, take = 0; k < 3 && i + k < n; ++k) {
  8.                 take += A[i + k];
  9.                 dp[i] = max(dp[i], take - (i + k + 1 < n ? dp[i + k + 1] : 0));
  10.             }
  11.         }
  12.         if (dp[0] > 0) return "Alice";
  13.         if (dp[0] < 0) return "Bob";
  14.         return "Tie";
  15.     }
  16. };
RAW Paste Data