Source: Max Non Negative SubArray

Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

Example:

A : [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]

NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length
NOTE 2: If there is still a tie, then return the segment with minimum starting index

解題：

  1. 這題其實還蠻簡單的，只要注意子陣列的取代條件及將所有複數作為子陣列統計之break point即可。而為了符合取代條件，需要另外儲存幾個資料：
    • 現階段加總值最大之子陣列及該子陣列長度
    • 目前迴圈統計之子陣列及其長度及加總值

Code:


def maxset(self, A):
    n = len(A)
    if n == 0: return []
    maximum, current_max =0, 0
    max_list, current_list = [], []
    for i in range(n):
        if A[i] >= 0: current_list.append(A[i])
        else:
            current_max = sum(current_list)
            if current_max > maximum or (current_max == maximum and len(current_list)>len(max_list)):
                maximum = current_max
                max_list = current_list
        current_list = []
    current_max = sum(current_list)
    if current_max > maximum or (current_max == maximum and len(current_list)>len(max_list)):
        maximum = current_max
        max_list = current_list
    return max_list

GitHub: GitHub

發表留言