Intuitive dp solution, explained.
Intuition\nSince k can vary a lot, and checking the answer for all possible k values is not possible. So, some way had to be thought to store answers till i ind
# Intuition\nSince ``k`` can vary a lot, and checking the answer for all possible ``k`` values is not possible. So, some way had to be thought to store answers till ``i`` index and then proceed ahead.\n\nAfter reading the problem, anyone can understand that only alterate values can be flipped from negative to positive or vice-versa. So, in this solution I tried to store both values...considering that ``i-1`` i.e prev index has been flipped and not flipped. \n\nWhen the previous index ``i-1`` has not been flipped then current index ``i`` can be flipped.\n\n# Approach\nHere,``vec`` vector stores the maximum total cost till ``i`` index considering both flip/non-flip of prev index cases. \n\nHere we have created a vector of ``pair<int, int>``, were first part stores the value considering ``i-1`` prev index has been flipped, and second part stores the value considering ``i-1`` index has not been flipped.\n\nSuppose the prev index i.e ``i-1`` has been flipped then\n``vec[i].first = nums[i] + max(vec[i-1].first, vec[i-1].second)``\ncurrent element cannot be flipped, but we can take max of both from previous index.\n\nSuppose the prev index i.e ``i-1`` has not been flipped then\n``vec[i].second = -nums[i] + nums[i-1] + max(vec[i-2].first, vec[i-2].second)`` flip the current element, take the prev element as it is, but we can take max of both from ``i-2`` index.\n\nAt the end simply return the max of both cases.\n\nHope the explanation made sense.\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    #define ll long long int\n    ll maximumTotalCost(vector<int>& nums) {\n        ll n = nums.size();\n        vector<pair<ll, ll>> vec(n, {0, 0});\n        vec[0].first = nums[0], vec[0].second = nums[0];\n        for(int i = 1; i<n; i++){\n            vec[i].first = nums[i] + max(vec[i-1].first, vec[i-1].second);\n            if(i <= 1) vec[i].second = -nums[i] + vec[i-1].first;\n            else vec[i].second = -nums[i] + nums[i-1] + max(vec[i-2].first, vec[i-2].second);\n        }\n        \n        return max(vec[n-1].first, vec[n-1].second);\n    }\n};\n```
['Dynamic Programming', 'C++']