Day 64 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/optimal-strategy-for-a-game-1587115620/1

Optimal Strategy For A Game
Difficulty: Medium Accuracy: 49.03%

You are given an integer array arr[] of size n. The array elements represent n coins of values v1, v2, ....vn.
You play against an opponent in an alternating way. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the coin's value.
You need to determine the maximum possible amount of money you can win if you go first.
Note: Both the players are playing optimally.

Examples:
Input: arr[] = [5, 3, 7, 10]
Output: 15
Explanation: The user collects the maximum value as 15(10 + 5). It is guaranteed that we cannot get more than 15 by any possible moves.
Input: arr[] = [8, 15, 3, 7]
Output: 22
Explanation: The user collects the maximum value as 22(7 + 15). It is guaranteed that we cannot get more than 22 by any possible moves.
Constraints:
2 <= n <= 103
1 <= arr[i] <= 106

Solution:
class Solution:
def maximumAmount(self, arr):
n = len(arr)
dp = [[0] * n for _ in range(n)]

    for length in range(1, n + 1):  # length of subarray
        for i in range(n - length + 1):
            j = i + length - 1
            if i == j:
                dp[i][j] = arr[i]
            elif length == 2:
                dp[i][j] = max(arr[i], arr[j])
            else:
                pick_first = arr[i] + min(dp[i+2][j], dp[i+1][j-1])
                pick_last = arr[j] + min(dp[i+1][j-1], dp[i][j-2])
                dp[i][j] = max(pick_first, pick_last)

    return dp[0][n-1]