Codility每周一课：L9 Maximum slice pr

9.png

P9.1 MaxSliceSum

Find a maximum sum of a compact subsequence of array elements.

• P9.1 最大子序列之和
  找到一个序列的最大子序列之和

编写函数：

def solution(A)

序列A的子序列是指在该序列A中拥有连续的数组下标的元素所组成的序列。对于给定的序列A, 返回它的最大子序列之和。

例如, 对于给定的序列A：A[0]=3，A[1]=2，A[2]=-6，A[3]=4，A[4]=0

可以得到下面的子序列:

[2,−6,4,0] [3,2,−6,4,0] [2] [3,2,−6] [−6,4] []以及其他的子序列。其中子序列[]被称为空的子序列, 因为其中不包含任何的元素。

下面的序列则不是给定序列A的子序列:[3,−6,0], [1], [3,2,−6,0]。

最大的子序列之和是指一个序列中所有非空的子序列的元素的总和的最大值. 用更精确的方式来表示:

max(A[p] + A[p+1] + ... + A[q] {其中p, q都是整数，并且p<q)

对于上面的序列A, 最大的子序列之和为：5 = A[0] + A[1]

假定:

1. N是区间[1，1,000,000]内的整数；

2. 数组A每个元素都是区间[−1,000,000，1,000,000]内的整数；

3. 最后所得的结果在区间[−2,147,483,648，2,147,483,647]中；

• 解题思路

如果只有一个元素，则返回其值。否则的话，则判断是不是均是负数，是的话，返回最大值即可。对于其他情况，定义一个存储和值的列表，如果当前的值为负数，则将之前的和值存储起来。如果之前的和值加上当前的值大于0，则更新之前的和值，否则的话，就将之前的和值存储起来。最后和值列表中最大的即为所求。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 9：Maximum slice problem
# P 9.1 MaxSliceSum


def solution(A):
    """
    返回序列A的子序列和的最大值
    :param A: 整数序列
    :return: 子序列和的最大值
    """
    if len(A) == 1:
        return A[0]
    else:
        max_num = max(A)  # 如果数组A中没有正数
        if max_num <= 0:
            return max_num
        else:
            sum_num = []  # 存储和值
            alive_sum = 0
            for i in A:
                if i < 0:
                    sum_num.append(alive_sum)
                alive_sum += i
                if alive_sum < 0:
                    sum_num.append(alive_sum - i)
                    alive_sum = 0
            sum_num.append(alive_sum)
            return max(sum_num)

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image