2 Soultions | DP | DFS/Recursion -> Memoization
Solution-1: (Recursion + Memo) -- (TLE -- 688 / 692 TCs passed -- 99.42%)\n### IDEA\n+ Simulte take & continue and take & end the subarray behaviour at each pos
# Solution-1: (Recursion + Memo) -- (TLE -- 688 / 692 TCs passed -- 99.42%)\n### IDEA\n+ Simulte `take & continue` and `take & end the subarray` behaviour at each position.\n+ The sign would be determined using -- `pow(-1, (i-l))`\n### Complexity: \n+ **Time:** O(N^2)\n+ **Space:** O(N^2)\n\n### CODE:\n```\n# define ll long long\nclass Solution \n{\nprivate:\n    vector<vector<ll>> dp;\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        // SOL-1: DFS/REC \n        // return dfs(nums, 0, 0);\n        \n        // SOL-2: MEMO\n        if ( isAllZeros(nums) )\n            return 0;\n        \n        dp = vector<vector<ll>>(nums.size()+1, vector<ll>(nums.size()+1, -1));\n        return memo(nums, 0, 0);\n    }\n\nprivate:\n    // MEMO -- 688 / 692 TCs passed -- 99.42%\n    ll memo(const vector<int>& nums, int i, int l)\n    {\n        if ( i >= nums.size() )\n            return 0;\n\n        if ( dp[i][l] != -1 )\n            return dp[i][l];\n\n        // take & continue.\n        ll ans1 = pow(-1, (i-l)) * (ll) nums[i] + memo(nums, i+1, l);\n        \n        // take & end the subarray.\n        ll ans2 = pow(-1, (i-l)) * (ll) nums[i] + memo(nums, i+1, i+1);\n        return dp[i][l] = max(ans1, ans2);\n    }\n    \n    bool isAllZeros(vector<int> &nums)\n    {\n        for ( int num : nums )\n            if ( num != 0 )\n                return false;\n        return true;\n    }\n    \n    ll dfs(const vector<int>& nums, int i, int l)\n    {\n        if ( i >= nums.size() )\n            return 0;\n        \n        // take & continue.\n        ll ans1 = pow(-1, (i-l)) * nums[i] + dfs(nums, i+1, l);\n        \n        // take & end the subarray.\n        ll ans2 = pow(-1, (i-l)) * nums[i] + dfs(nums, i+1, i+1);\n        return max(ans1, ans2);\n    }\n};\n```\n\n\n# Solution-2: (Recursion + Memo) -- (100% TCs pass)\n### IDEA\n+ The key obseravtion here is that if number is positive we could always start a new subarray from there.\n+ Hence, no need to keep track of previous element index. Instead we could just track flip to determine the sign (+ve or -ve). Thereby reducing time from Quadratic to linear.\n### Complexity: \n+ **Time:** O(2*N) --> O(N)\n+ **Space:** O(2*N) --> O(N).\n### CODE:\n```\n# define ll long long\nclass Solution \n{\nprivate:\n    vector<vector<ll>> dp;\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        // SOL-1: DFS/REC  -- 629 / 692 TCs passed -- 90.89%\n        // return dfs(nums, 0, 0);\n        \n        // SOL-2: MEMO -- 100% TCs passed.\n        dp = vector<vector<ll>>(nums.size()+1, vector<ll>(3, -1));\n        return memo(nums, 0, 0);\n    }\n\nprivate:\n    ll memo(const vector<int>& nums, int i, int f)\n    {\n        if ( i >= nums.size() )\n            return 0;\n\n        if ( dp[i][f] != -1 )\n            return dp[i][f];\n\n        // take & continue.\n        ll ans1 = -1e15;\n        if ( f == 1 ) ans1 = (ll) -nums[i] + memo(nums, i+1, 0);\n        \n        // take & end the subarray.\n        ll ans2 = (ll) nums[i] + memo(nums, i+1, 1);\n        return dp[i][f] = max(ans1, ans2);\n    }\n    \n    ll dfs(const vector<int>& nums, int i, int f)\n    {\n        if ( i >= nums.size() )\n            return 0;\n        \n        // take & continue.\n        ll ans1 = -1e15;\n        if ( f == 1 ) ans1 = -nums[i] + dfs(nums, i+1, 0);\n        \n        // take & end the subarray.\n        ll ans2 = nums[i] + dfs(nums, i+1, 1);\n        return max(ans1, ans2);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']