C++ Modified Kadane's
I find it is easiest to break DP problems down into the choices at every step. In the original Maximum Subarray problem, at every index, we can either begin a n
I find it is easiest to break DP problems down into the choices at every step. In the original Maximum Subarray problem, at every index, we can either begin a new subarray, or keep adding on to our current one. In this problem, we now have another choice: skip the current element.\n\nIn the original Maximum Subarray problem, we can solve it by keeping track of the maximum subarray ending at every index `i`. We can do the same here by in addition keeping track of the maximum "skipped" subarray ending at position `i`.\n\n```\nint maximumSum(vector<int>& arr) {\n\tif (arr.size() == 0) return 0;\n\tint max_sum = arr[0];\n\tint current_sum = arr[0];\n\tint skipped_current_sum = 0;\n\tfor (int i = 1; i < arr.size(); ++i) {\n\t\tskipped_current_sum = max(skipped_current_sum + arr[i], current_sum);\n\t\tcurrent_sum = max(arr[i], current_sum + arr[i]);\n\t\tmax_sum = max(max_sum, max(current_sum, skipped_current_sum));\n\t}\n\treturn max_sum;\n}\n```
['Dynamic Programming', 'C']