HackerRank The Maximum SubArray

Question

So I am attempting to go through the Dynamic Programming track on HackerRank.

Problem prompt is as follows.

Given an array A={a1,a2,…,aN} of N elements, find the maximum possible sum of a

Contiguous subarray Non-contiguous (not necessarily contiguous) subarray. Empty subarrays/subsequences should not be considered.

Input Format

First line of the input has an integer T. T cases follow. Each test case begins with an integer N. In the next line, N integers follow representing the elements of array A.

Contraints:
$1 <= T <= 10$
$1 <= N <= 10^5$
$-10^4 <= a_i <= 10^4$

The subarray and subsequences you consider should have at least one element.

Output Format

Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).

Sample Input

2 
4 
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output

10 10
10 11

Explanation
In the first case: The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).

In the second case: [2 -1 2 3 4] --> This forms the contiguous sub-array with the maximum sum. For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.

My solution to this was

def dp2(L):
    max_so_far = max_ending_here = -2**31 # contig logic works
    non_contig = [L[0]] # accounting for negative arrays

    for i in xrange(len(L[0::])):
        max_ending_here = max(L[i], max_ending_here + L[i])        
        max_so_far = max(max_so_far, max_ending_here) 
        # non-contiguous logic
        if i != 0:
            non_contig.append(max(non_contig[-1], non_contig[-1] + L[i]))   
    return map(str, (max_so_far, non_contig[-1]))

if __name__ == '__main__':
    test_cases = int(raw_input())
    for i in xrange(test_cases):
        arr_length = int(raw_input())
        array = [int(i) for i in raw_input().split()] 

        print ' '.join(dp2(array))

So the above code passes all but one test-case. Which is very large and so I decided to upload all of the test-cases into a unittest and run on my local environment to see what was going on.

This

.F..
======================================================================
FAIL: test_answers_against_test_case2_outputs (__main__.TestCase2)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "test_max_subarray.py", line 52, in test_answers_against_test_case2_outputs
    self.assertEqual(result, self.outputs[idx])
AssertionError: Lists differ: ['2617065', '172073086'] != [u'2617065', u'172083036']

First differing element 1:
172073086
172083036

- ['2617065', '172073086']
?                  ^  ^

+ [u'2617065', u'172083036']
?  +           +     ^  ^


----------------------------------------------------------------------
Ran 4 tests in 0.951s

FAILED (failures=1)

There are two digits that are incorrect in regards to the non-contiguous answers the dp function is spitting out. Could this be an issue of converting from ints to strings?

I realize that I am comparing unicode to python strings but it doesn't seem to matter as I have tried it the other way around so I do not think that is the issue but I could be wrong.

trendsetter37 · Accepted Answer · 2015-09-25 22:52:00Z

I know where I went wrong. For the non-contiguous logic it totally slipped my mind that I could simply set the current sum to 0 and only attempt to add positive integers to that.

If all of the integers within the given array are negative then simply get the max and return that as the max sum.

Working code.

def dp(L):
    max_so_far = max_ending_here = -2**31
    c_sum = 0
    max_neg = -2**31

    for i in xrange(len(L)):
        max_ending_here = max(L[i], max_ending_here + L[i])        
        max_so_far = max(max_so_far, max_ending_here)

        if L[i] > 0:
            c_sum += L[i] 
        else:
            if L[i] > max_neg:
                max_neg = L[i]
    if c_sum == 0: # All values were negative so just pick the largest
        c_sum = max_neg
    return map(str, (max_so_far, c_sum))

if __name__ == '__main__':
    test_cases = int(raw_input())
    for i in xrange(test_cases):
        arr_length = int(raw_input())
        array = [int(i) for i in raw_input().split()]

        print ' '.join(dp(array))

Instead of using python's max function outside of the for loop I opted to just keep track of such within the loop to try and keep the runtime close to O(n).

Collectives™ on Stack Overflow

HackerRank The Maximum SubArray

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related