Java Dp and without Dp solution with explanation
Intuition\nAt each index we can \n-> start a new subarray with the current index or\n-> it would be part of the previous subarray. \n\nWe find maximum sum at ea
# Intuition\nAt each index we can \n-> start a new subarray with the current index or\n-> it would be part of the previous subarray. \n\nWe find maximum sum at each index using the above two points.\n\n# Approach\nlet dp[n] be the maximum sum at each index of the array.\n\nusing the two points in the intutuion :\n\nstarting the subarray with the current index: \ndp[currentIndex] = Math.max(dp[currentIndex], dp[currentIndex] + dp[currentIndex-1])\n\nit would be part of a previous subarray:\ndp[currentIndex] = Math.max(dp[currentIndex], dp[currentIndex-1] - dp[currentIndex] + dp[currentIndex-2])\n\nHow I got to this is:\n\nLets say we are at index k.\n\nif \'K\' is part of previous subarray it must either fall in a even postion or odd postion \nlets say s is the starting index of the a subarray where k is part of it \n (-1)^(k-s) : if k-s is even then its on even postion\n              if k-s is odd then its on odd position\n\nlets say if (s-k) is even then (s-k) is even position, \nthen \ndp[k] = nums[s] - nums[s+1] + nums[s+2].... - nums[k-1] + nums[k]\ndp[k] = nums[k] + dp[k-1]\nIf k is on even postion, then we can start the subarray at k as it is also an even postion.\n\nif (s-k) is odd then k is on odd position,\nIf we consider k-1 as start index instead of s. then K is still on the same odd position which doesn\'t effect the k\' position.\n\ndp[k] = nums[s] - nums[s+1] + .... + nums[k-1] - nums[k]\ndp[k] = dp[k-2] + nums[k-1] - nums[k]\n\nwe cannot directly use dp[k] = dp[k-1] - nums[k] as dp[k-1] also includes the value of k-1 at odd position, as K is in odd position K-1 must be on even position.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n    public long maximumTotalCost(int[] nums) {\n        \n        int n = nums.length;\n\n        long dp[] = new long[n];\n        \n        dp[0] = nums[0];\n        for(int i=1;i<n;i++)\n        {\n            dp[i] = Math.max(dp[i], nums[i] + dp[i-1]);\n\n            if(i-2>=0)\n                dp[i] = Math.max(dp[i], nums[i-1] - nums[i] + dp[i-2]);\n        }\n\n        return dp[n-1];\n    }\n}\n\n```\n\nSpace optimizing, just using the previous value and previous\'s previous value\n\n```\n\nclass Solution {\n    public long maximumTotalCost(int[] nums) {\n        \n        int n = nums.length;\n\n        long prev=nums[0], prevsprev=0;\n        \n        for(int i=1;i<n;i++)\n        {\n            long curSum = nums[i] + prev;\n            \n            curSum = Math.max(curSum, nums[i-1] - nums[i] + prevsprev);\n\n            prevsprev = prev;\n            prev = curSum;\n        }\n\n        return prev;\n    }\n}\n\n```\n\nIf you like the solution, do upvote
['Java']