maximum subarray of an array with integers [duplicate]

by

Your solution is O(n^2). The optimal solution is linear. It works so that you scan the array from left to right, taking note of the best sum and the current sum:

def get_max_sum_subset(x):
    bestSoFar = 0
    bestNow = 0
    bestStartIndexSoFar = -1
    bestStopIndexSoFar = -1
    bestStartIndexNow = -1
    for i in xrange(len(x)):
        value = bestNow + x[i]
        if value > 0:
            if bestNow == 0:
                bestStartIndexNow = i
            bestNow = value
        else:
            bestNow = 0

        if bestNow > bestSoFar:
            bestSoFar = bestNow
            bestStopIndexSoFar = i
            bestStartIndexSoFar = bestStartIndexNow

    return bestSoFar, bestStartIndexSoFar, bestStopIndexSoFar

This problem was also discussed thourougly in Programming Pearls: Algorithm Design Techniques (highly recommended). There you can also find a recursive solution, which is not optimal (O(n log n)), but better than O(n^2).

More Related Contents:

  1. How do I search for a number in a 2d array sorted left to right and top to bottom?
  2. Quicksort: Choosing the pivot
  3. Generate an integer that is not among four billion given ones
  4. Breadth First Vs Depth First
  5. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  6. Time complexity of Euclid’s Algorithm
  7. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  8. Quick sort Worst case
  9. Is there an efficient algorithm to generate a 2D concave hull?
  10. How to round floats to integers while preserving their sum?
  11. Modulus power of big numbers
  12. Fast algorithm implementation to sort very small list
  13. Compute social distance between two users
  14. Efficient algorithm for ordering different types of objects
  15. How to find two most distant points?
  16. Algorithm to find two repeated numbers in an array, without sorting
  17. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  18. How to implement depth first search for graph with a non-recursive approach
  19. Why is the time complexity of both DFS and BFS O( V + E )
  20. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  21. Mesh generation from points with x, y and z coordinates
  22. How do you find a point at a given perpendicular distance from a line?
  23. How to find distance from the latitude and longitude of two locations?
  24. Algorithm for sampling without replacement?
  25. Bits counting algorithm (Brian Kernighan) in an integer time complexity
  26. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  27. determine if a point sits inside an arbitrary shape?
  28. Binary tree level order traversal
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment