[C++] Shortest DP solution with explanation | O(N) time O(1) space
We follow a similar approach to Kadane\'s algorithm here.\n\nIn each interation for index i,\ncurr0 is the maximum sum subarray ending at index i where no eleme
We follow a similar approach to Kadane\'s algorithm here.\n\nIn each interation for index i,\n`curr0` is the maximum sum subarray ending at index i where no element is excluded\n`curr1` is the maximum sum subarray ending at index i  where one element is excluded\n`prev0` is the maximum sum subarray ending at `index i-1` where no element is excluded\n`prev1` is the maximum sum subarray ending at `index i-1`  where one element is excluded\n\n**Initialisation:** prev0 is the first element and prev1 is 0 as the first element is excluded\n\nIn each iteration we calculate curr0 & curr1, and update prev0 & prev1.\nTo update curr0 we follow the same logic as Kadane\'s - either extend the previous subarray or start a new one.\nTo update curr1 we have two options,\n1. either exlude the current element and use prev0\n2. or include current element and add it to prev1\n\n\n```\n#define ll long long\n\nclass Solution {\npublic:\n    int maximumSum(vector<int>& a) {\n        ll ans = a[0], prev0 = a[0], prev1 = 0;\n        \n        for(int i = 1 ; i < a.size() ; i++) {\n            ll curr0 = a[i] + max(prev0, 0ll);\n            ll curr1 = max(a[i] + prev1, prev0);\n            ans = max({ans, curr0, curr1});\n            \n            prev0 = curr0;\n            prev1 = curr1;\n        }\n        \n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C']