Java | 2 methods | Explained
Method 1: Bottom Up DP (Tabulation)\n Aim is to maximize MS = values[i] + values[j] + i - j for i < j, which can be rewritten as S + D where S = values[i] + i, 
**Method 1:** Bottom Up DP (Tabulation)\n* Aim is to maximize MS = values[i] + values[j] + i - j for i < j, which can be rewritten as S + D where S = values[i] + i, D = values[j] - j, MS = max score\n* So if we maximize both S and D, then MS will be maximized\n* Use a 1D table to store the maximum value of S seen till any index. Then use this max value to maximize D, thereforce MS\n\n![image](https://assets.leetcode.com/users/images/c72bc0af-d957-4204-974b-9581d1327157_1660765142.0492387.png)\n\n>**T/S:** O(n)/O(n), where n = size(values)\n```\npublic int maxScoreSightseeingPair(int[] values) {\n\tvar maxScore = 0;\n\tvar n = values.length;\n\tvar dp = new int[n];\n\tdp[0] = values[0];\n\n\tfor (var i = 1; i < n; i++) {\n\t\tmaxScore = Math.max(maxScore, dp[i - 1] + values[i] - i);\n\t\tdp[i] = Math.max(dp[i - 1], values[i] + i);\n\t}\n\treturn maxScore;\n}\n```\n\n**Version 2:** Space optimize method 1 since only 1 previous value is being used\n>**T/S:** O(n)/O(1)\n```\npublic int maxScoreSightseeingPair(int[] values) {\n\tvar maxScore = 0;\n\n\tfor (int i = 1, sumMax = values[0]; i < values.length; i++) {\n\t\tmaxScore = Math.max(maxScore, sumMax + values[i] - i);\n\t\tsumMax = Math.max(sumMax, values[i] + i);\n\t}\n\treturn maxScore;\n}\n```\n***Please upvote if this helps***
['Dynamic Programming', 'Java']