See the original problem on HackerRank.
Solutions
We have two similar tasks:
 find the maximum sum of any nonempty subarray
 find the maximum sum of any nonempty subsequence
The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment.
To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element.
What if we have all negative values? The max sum is just the biggest value (the one closest to zero).
Here is the idea in Python:


Here is a similar approach in C++:


Clearly, we might iterate only once but we like showing the patterns which shape the solution.
Just for completeness, the algorithm above is greedy and takes linear time.
Now, we can face with the other  more difficult  task: the maximum sum of any nonempty subarray.
A quadratic solution exists: we run two loops. The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. Finally return the overall maximum.
Clearly, we are interested in a better approach.
A simple idea is to look for all positive contiguous segments of the array (max_ending_here
is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far
is used for this). Each time we get a positive sum compare it with max_so_far
and update max_so_far
if it is greater than max_so_far
.
Here is some C++ code:


This solution is called as Kadane’s Algorithm and the time complexity is linear. Kadane’s algorithm is usually used to explain the basics of Dynamic Programing that is is one of the problem solving paradigms where we try to find a solution by breaking the larger problem into subproblems.
As Marco Arena noted, Kadane’s algorithm can be rewritten as the combination of two patterns:
 prefix sum (with a special binary function)
 maximum
So here is a possible C++ alternative (clearly, it does two iterations and changes the original array):


In C++20 this solution can be implemented elegantly and efficiently (single pass) with ranges:


Not shown here, there is another interesting solution which adopts the Divide and Conquer approach. Find it here.
So, here is a complete solution:


A complete solution is also found on HackerRank:

