Java | O(n) | solved with intuition | approach explained
Sorry for the bad handwritting, I am learning to use digital pen :)\nThis can be optimised more, I just thought to share a intuition behind solving this problem
Sorry for the bad handwritting, I am learning to use digital pen :)\nThis can be optimised more, I just thought to share a intuition behind solving this problem.\n![image](https://assets.leetcode.com/users/images/0df0f8ca-b948-4b6c-b507-76f912deeed9_1640765892.1186037.png)\n\n```\nclass Solution {\n    public int maxScoreSightseeingPair(int[] values) {\n        int len = values.length;\n        \n        int[] maxLeft = new int[len];\n        int[] maxRight = new int[len];\n        \n        int prev = 0;\n        for(int i=0;i<len-1;i++){\n            int val = i+values[i];\n            if(val>prev){\n                maxLeft[i] = val;\n                prev = val;\n            }else{\n                maxLeft[i] = prev;\n            }\n        }\n        \n        prev = Integer.MIN_VALUE;\n        for(int i=len-1;i>0;i--){\n            int val = values[i]-i;\n            if(val>prev){\n                maxRight[i] = val;\n                prev = val;\n            }else{\n                maxRight[i] = prev;\n            }\n        }\n        \n        return calc(maxLeft,maxRight);\n    }\n    \n    int calc(int[] left, int[] right){\n        int sum = 0;\n        int max = 0;\n        for(int i=0;i<left.length-1;i++){\n            sum = left[i]+right[i+1];\n            max = Math.max(sum,max);\n        }\n        return max;\n    } \n}\n```
[]