问题陈述

Problem Statement:

You have been given an array containg numbers. Find and return the largest sum in a contiguous subarray within the input array.

Example 1: * arr= [1, 2, 3, -4, 6] * The largest sum is 8, which is the sum of all elements of the array.

Example 2: * arr = [1, 2, -5, -4, 1, 6] * The largest sum is 7, which is the sum of the last two elements of the array.

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def find_first_positive(input_list):
    for i in range(len(input_list)):
        if input_list[i] > 0:
            return i
def max_sum_subarray(input_list):
    if input_list is None:
        return None
    max_sum = input_list[find_first_positive(input_list)]
    sum_arr = input_list[find_first_positive(input_list)]
    flag = True
    for i in range(find_first_positive(input_list)+1, len(input_list)):
        if max_sum + input_list[i] > max_sum and flag:
            max_sum += input_list[i]
        else:
            flag = False
        if sum_arr + input_list[i] > 0:
            sum_arr += input_list[i]
        else:
            sum_arr = input_list[i]
        if sum_arr > max_sum:
            max_sum = sum_arr
            flag = True
#         print('max_sum', max_sum)
#         print('sum_arr', sum_arr)
    return max_sum

测试用例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def test_function(test_case):
    arr = test_case[0]
    solution = test_case[1]
    
    output = max_sum_subarray(arr)
    if output == solution:
        print("Pass")
    else:
        print("Fail")

arr= [1, 2, 3, -4, 6]
solution= 8 # sum of array

test_case = [arr, solution]
test_function(test_case)

arr = [1, 2, -5, -4, 1, 6]
solution = 7   # sum of last two elements

test_case = [arr, solution]
test_function(test_case)

arr = [-12, 15, -13, 14, -1, 2, 1, -5, 4]
solution = 18  # sum of subarray = [15, -13, 14, -1, 2, 1]
test_case = [arr, solution]
test_function(test_case)