SubArray

def mid_subarray(array, left, right, mid) :
    '''
        计算介于mid左右的最大子序列
        返回子序列左右下标以及各元素之和
    '''
    left_sum = array[mid]
    left_max = left_sum
    left_index = mid
    right_sum = array[mid + 1]
    right_max = right_sum
    right_index = mid + 1
    for i in range(mid - 1, left - 1, -1) :
        left_sum += array[i]
        if (left_sum > left_max) :
            left_max = left_sum
            left_index = i
    for j in range(mid + 2, right + 1) :
        right_sum += array[j]
        if (right_sum > right_max) :
            right_max = right_sum
            right_index = j
#若mid一侧的子序列元素和小于0，则忽略
#若均小于0，则取较大者
    if (right_max <= 0) or (left_max <= 0 and right <= 0 and right_max < left_max) :
        right_index = mid + 1
        sum = left_max
    elif (left_max <= 0) or (left_max <= 0 and right <= 0 and left_max < right_max) :
        left_index = mid
        sum = right_max
    else :
        sum = left_max + right_max
    return left_index, right_index, sum

def subarray(array, left, right) :
    '''
    '''
    if (left == right) :
        return left, right, array[left]
    else :
        mid = int((left + right) / 2)
        left_low, left_high, left_sum = subarray(array, left, mid)
        right_low, right_high, right_sum = subarray(array, mid + 1, right)
        mid_low, mid_high, mid_sum = mid_subarray(array, left, right, mid)
        if (left_sum >= right_sum and left_sum >= mid_sum) :
            return left_low, left_high, left_sum
        elif (right_sum >= left_sum and right_sum >= mid_sum) :
            return right_low, right_high, right_sum
        else :
            return mid_low, mid_high, mid_sum

def iteration(array, n) :
    sum = 0
    max = 0
    left = 0
    right = n - 1
    for i in range(n) :
        sum = 0
        for j in range(i, n) :
            sum += array[j]
            if sum > max :
                max = sum
                left = i
                right = j
    return left, right, max


array = [13, -3,-25,25,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
print (subarray(array, 0, len(array) - 1))
print (iteration(array, len(array) - 1))