 # DCP49 - Subarray with max sum

Oct 22nd, 2020
728
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. This problem was asked by Amazon.
3. Given an array of numbers, find the maximum sum of any contiguous subarray of the array.
4. For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.
5. Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.
6. Do this in O(N) time.
7. '''
8.
9. # Function 1
10. def solve(array):
11.     # ******************************************************************************
12.     # ALL THE ITEMS RETURNED WILL BE TUPLES WITH 2 ELEMENTS
13.     # 1ST WILL BE THE MAX SUM AND SECOND THE LIST FROM WHICH THIS MAX SUM COMES FROM
14.     # ******************************************************************************
15.     n = len(array)
16.     if n == 1:
17.         if array < 0:
18.             print("The array " + str(array) + " has only one element, that is also negative (" + str(array) + "), so answer = 0 (must be positive or zero)")
19.             return 0, 
20.         else:
21.             return array, [array]
22.     # Here, we go for n >= 2
23.     maxSum = 0
24.     maxList = list()
25.     for elementsTaken in range(n-1, 0, -1):
26.         # Example ----> I take 5 elements (2 possible lists if my array is length = 6)
27.         for firstIndex in range(0, n + 1 - elementsTaken):
28.             SUMLIST = list()
29.             # i = first index between the consecutive elements
30.             for i in range(elementsTaken):
31.                 SUMLIST.append(array[firstIndex+i])
32.             if sum(SUMLIST) > maxSum:
33.                 maxSum = sum(SUMLIST)
34.                 maxList = SUMLIST.copy()
35.
36.     return maxSum, maxList
37.
38.
39. # FUNCTION 2
40. def prettyPrint(array):
41.     SUM, SUMLIST = solve(array)
42.     # I want to check the special case of having only one negative element in my array (SUM = 0)
43.     print(str(array) + " ----> The sublist " + str(SUMLIST) + " has the elements with max sum = " + str(SUM))
44.
45. # MAIN FUNCTION
46. array0 = 
47. array1 = 
48. array2 = [-10]
49. array3 = [10, 40]
50. array4 = [100, 25]
51. array5 = [34, -50, 42, 14, -5, 86]
52. array6 = [10, -3, 28, 9, -10, 8, -20, 18]
53. array7 = [-5, -1, -8, -9]
54. arrays = [array0, array1, array2, array3, array4, array5, array6, array7]
55. for i in range(len(arrays)):
56.     print("******** " + str(i+1) + " ********")
57.     prettyPrint(arrays[i])
58.     print()
RAW Paste Data