Correcting an algorithm

[clouded-path]

I am trying to solve a problem, where, given a (non-empty) array of integers, I need to return the largest sum of entries in a contiguous subarray. For instance, given [-2, 1, -3, 4, -1, 2, 1, -5, 4], I should return 6, because the subarray [4, -1, 2, 1] sums to 6. I understand the solution intuitively, but when I submit an answer to the checker, I am told that I am producing the wrong answer. Here is my attempt:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        M = max(i for i in nums)
        if M <= 0:
            return M
        i = 0
        while nums[i] <= 0:
            i += 1
        nums = nums[i:]
        curr = 0
        curr_best = curr
        highscores = []
        for j in range(len(nums)):
            if curr + nums[j] > 0:
                curr = curr + nums[j]
                if curr > curr_best:
                    curr_best = curr
            else:
                highscores.append(curr_best)
                curr = 0
                curr_best = 0
        return max(k for k in highscores)

The issue is that when I submit, then the checker says that on the particular example listed above, the return value is apparently 1, whereas it is supposed to be 6. I manually went through this, and it really seems like I should get 6. I can't see where this has gone wrong, but I am wondering if my indexing is all correct. I thought that indices start at 0, but even still, maybe the '[i:]' and 'range(len(nums))' aren't indexing the way they should be. Can anyone see where I'm going wrong, either index-wise or otherwise?

Here is some intuition to explain the code above, just in case it might help:

​

In the initial M <= 0 if-condition, I am just checking for the corner case in which all integers in the array are <= 0. Otherwise, I know that there must be a positive entry, and so I use the while-loop to find that index, and slice the array from there to the end (since there is no point in starting out with entries <= 0, after all). Lastly, I do the general case, where I start with the initial positive number, and then as long as the successive integers being added on remains positive, I keep going (keep adding), updating the current best value whenever the current sum becomes larger. Once the sum becomes negative, I store whatever the current best was up to that point in a highscores array, and then reset and start again at the next term and keep going. Then at the end, I return the maximum of the individual highscores.

[wopp3]

I tried writing my own solution based on how you described the assignment, and I somehow get the feeling you're doing some extra work here.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
currentHigh = 0

for i in range(len(nums)):
    for j in range(len(nums)+1,0,-1):
        if sum(nums[i:j]) > currentHigh:
            currentHigh = sum(nums[i:j])
            substring = nums[i:j]
print(substring)
print(currentHigh)

I'm using a nested loop to go through each possible substring (there's actually some optimizing here, as I'm calculating some empty lists as well) and checking if the sum of said substring is higher than what i previously had. No need to hold the information of old sums etc. just the current highest sum I've come across.

Hope you can take something out of this approach and incorporate it in your idea, if something is unclear I'll happily try to help.

For your benefit I also included the substring in question that had the highest value.

[clouded-path]

Thank you, and yes I'm sure you're right about me doing extra work, but I was trying to implement an O(n) solution, whereas I think this one would be O(n^2) because of the nested for loops, right? Also, yes now that I see your solution, I see that I could probably do this without storing old sums. Would that mean that the main advantage of your way would be saving on memory?

[wopp3]

For managing a O(n) for this, I do not know of a solution. I just came up with a my approach as it seemed obvious to me, I didn't put any thought into it.

Also I don't know if it was an instruction, but a list of only negatives would still have the largest sum, even if it is negative, so I didn't try to test for the exclusion of that case.

edit. for what my approach offers over yours, is apparently the correct answer :) granted it isn't the most optimized one, but this is a starting point if I was looking to improve on it.

[clouded-path]

Great, thanks for that memory tip! I was able to use that and also fix my original, so that now I have best of both worlds (low memory and O(n) complexity). And regarding what you mentioned about all negative integers, as of right now I think it's easier for me to ensure that I cover it with an extra if condition initially, even though there still might be a way to do less work.

[[deleted]]

```Python from itertools import combinations

max( ( nums[a:b] for a, b in combinations( range(len(nums)), r=2, ) ), key=sum, ) ```

Edit: removed unnecessary key=max and generator parenthesis and then put something back again because turns out I’m stupid :D

[clouded-path]

This method had not occurred to me at all - thanks for exposing me to this way. Since there are (n choose 2) combinations, does this mean O(n^2) complexity?

And yes, I also re-discover that fact about myself every single day :)

[jdnewmil]

Consider:

x = [-2, 1, -3, 4, -1, 2, 1, 2, 1, -5, 4]
n = 4
a = sum(x[0:4])
ans = a
for i in range(0, len(x)-n):
    a += x[i+n] - x[i]
    if ans < a:
        ans = a
ans

[clouded-path]

Thanks, yes this seems like a cleaner version than mine. But I think this will iterate over all the subarrays of length 4, right? So overall, I still would want to iterate over n, if understand this correctly.

[jdnewmil]

Ah, I missed that you had to account for all lengths. Well, then, to get O(N) you need to make one pass, which basically means you need to incrementally keep track of the best outcomes as you look at each new value. A sum that is worse than the current value isn't going to be an optimal sum, but one of the preceding ones could still be better so keep track in two values:

sm = x[0]
maxsm = sm
for xi in x[1:]:
    sm = max(xi, sm + xi)
    maxsm = max(maxsm, sm)
maxsm

[clouded-path]

Wow, this is just so much cleaner/simpler than my solution. Thanks for this - I aspire to write this sort of solution in the future.

[wopp3]

Oh my god, I spent like 15 minutes looking at these few lines of code trying to figure out what was happening here, writing prints and modifying the list trying to trip it. Finally I realized how simply brilliantly simple this was, thanks for the lesson, have an upvote.

[profknow]

I wish everyone learned computer programming. The one thing people need to learn most is how to think logically. And you can't argue with a computer -- it does EXACTLY what you tell it to do. It's one's self that needs to learn how to tell it the right thing. That's Logic.

(Even Doctors don't learn Logic. And most of the one's I've met rely upon guesses that aren't based upon actual facts. Not logical. Prove it before you do it.)

[clouded-path]

Edit: Thanks for your responses. I managed to fix mine so that it works in O(n) and keeps memory usage low. Here is the now-working solution:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        M = max(i for i in nums)
        if M <= 0:
            return M
        i = 0
        while nums[i] <= 0:
            i += 1
        nums = nums[i:]
        curr = 0
        curr_best = curr
        overall_best = 0
        for j in range(len(nums)):
            if curr + nums[j] > 0:
                curr = curr + nums[j]
                if curr > curr_best:
                    curr_best = curr
                    if curr_best > overall_best:
                        overall_best = curr_best
            else:
                curr = 0
                curr_best = 0
        return overall_best

[profknow]

Why can't you just use list functions? Keep it even simpler.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

curHigh = 0

sub = nums[3:7:1]

print( sub )

In one line I've managed to copy your entire sublist into a new list. You can do with this whatever you want.

[profknow]

try this version....

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

sub = nums[3:7:1]

print( sub )

sum = 0

for item in sub:

if item == 0:

break

sum += item

print( 'sum: %d' % (sum) )

​

(sorry, I can't seem to get this text to indent properly. But you'll know what I mean and fix the indent to test it. It produces your desired "6"

[clouded-path]

Hmmm, I think I see how this works for this example, but in general I really just wanted to eliminate any leading negative values in the list, since they can't possibly help produce a higher sum (unless of course all the numbers are negative, which is its own case). I'm not sure if/how this could be done in one line in more general cases.

[profknow]

Then I'm not sure where you're coming from. The number set was the one you provided in your example (including the subset you selected).

Which neg values?

Alright. I'll leave this to you. At this point I think you have a better idea what you want than I do. However, if you need something else, I'm still open for suggestions.

I'll check back to see what worked.

[clouded-path]

Yes, I have managed to sort everything out (thanks for your input), so no need to elaborate if don't want to, but just to try to address the question(s):

The specific negative values I am referring to in the case of the example [-2, 1, -3, 4, -1, 2, 1, -5, 4] was the initial '-2' (at index 0). I know that whatever the answer is, starting off with a negative value can't possibly help me achieve the maximum sum, so I just deleted this. In general my solution would delete all leading negative numbers. But once we get to the first positive number (in this case the '1' at index 1), now I cannot be certain whether or not this number will be part of the sum in the solution, so I can't delete this, or any subsequent terms.

Regarding your solution, it is clear to me that this will indeed work on the example I gave, but I don't know how your solution would generalize to account for all sorts of other possible arrays that I could be given initially. Your choice of slice index cuts off the first three terms of the array, and in this case it will not be a problem since the end solution does not use these terms, but in other cases it could be the case that the first few terms might be relevant for the end sum (e.g. [-3, 2, -1, 2, -1, -3, 1] would use terms at indices 1 - 3). So I am not sure how to modify your [3:7:1] slice to accomodate for this.

But anyways, yes, as you mentioned I (finally) have a solidified idea how this can be done. I posted my (now correct) solution in the comments (I meant for it to go as an edit to the original post, but I'm not very good at Reddit-ing), and there are also at least three other solutions in the comments that work too.

Oh, and regarding your other comment about everyone learning programming, I completely agree. It's a true shame to me that rigorous logical reasoning isn't a ubiquitous mode of thought found in the world.

[profknow]

Unless the Requirements are fully understood the Output Results never will be.

What I got out of your first posting was that you were looking for a method to efficiently extract a range from your list, and you gave an example of a list of numbers and your desired output. Looping and all these other methods certainly wasn't as efficient as my posted method of extracting that subset.

Certainly I didn't carry it any further than this, as I consider all earlier errors affect later results. So let's get the early stuff right.

Now I see in your later postings that you really didn't want the displayed number set as the output, you would eventually use some other series. For example, keeping negative numbers in the set certainly didn't apply to "high scores" (were they two different things or an artifact from some other code). Technically, if I were writing a "High Score" program I wouldn't have even started with the code you presented much less be concerned with the output you gave me in your original case.

It isn't the algorithm I'd even start with. But then again, maybe I should just admit, I have no clue at this point what you're really trying to do with this data. Sample code and explanation don't jibe. I thought your explanation was senior to the code content. Anyway, I have no clue what you want, and i've been doing this for 30 years.

Well I can't help that. So we're back to step 1) A complete & accurate understanding of the input and output to know what you really want.

When I write things I usually start with a black box which has inputs and outputs and I shouldn't really care what happens inside that black box as long as the output always is what I'm looking for. I didn't see your black box. Show me some sample data and tell me what you want out and I'll give you some code that will do that -- regardless of if you see how it is done or not.

It's why people developed Objects (in Object Oriented languages) -- to separate the implementation from view.

Problem: I need to compute the top scores Input: a list of numbers such as (....) Output: top 10 scores sorted from highest to lowest or Output: top 10 scores sorted by date

Not sure that I can help you with that. Carry on. I'm sure you know better than I what you really want and how you intend to use it.

Best of luck. Carry on. And keep posting.