Silver: Maximum Subarray Sum (Prefix Sum)

Link to the question:

I’m a little confused on how to solve it. Here is what I’m thinking right now. First I’ll create a prefix array given the input array. Now I’m confused on how to find the max subarray sum, won’t I have to try every combination of sum to find the maximum one? Or is there a more efficient way of finding the maximum subarray sum?

Please let me know!

First, create the prefix sum. Next, have two variables: the answer and the current smallest subarray. Now, loop through the prefix sum. Each iteration, the answer is the max between the answer and the current subarray minus the current smallest subarray; the smallest subarray is the current smallest subarray or the current subarray. Hope this helps :slight_smile:

Use Kadane’s Algorithm

Using Kandane’s Algorithm like explained by InterviewBit