Codility每周一课：L9 Maximum slice pr

9.png

P9.3 MaxDoubleSliceSum

Find the maximal sum of any double slice.

• P9.3 双切片最大和
  计算所有双切片的最大和

一个由N个整数组成的非空数组A。三元组(X, Y, Z)，满足0 ≤ X < Y < Z < N，则称为双切片。双切片(X, Y, Z)之和是A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

例如，数组A：

A[0]=3，A[1]=2，A[2]=6，A[3]=-1，A[4]=4，A[5]=5，A[6]=-1，A[7]=2

给出以下双切片的示例：

1. 双片（0，3，6），和为2+6+4+5=17，

2. 双片（0、3、7），和为2+6+4+5−1=16，

3. 双片（3，4，5），和为0。

目标是找到所有双切片的和中的最大值。

编写函数：

def solution(A)

给定一个由N个整数组成的非空数组A，则返回其所有双切片和中的最大值。

例如，给定A：

A[0]=3，A[1]=2，A[2]=6，A[3]=-1，A[4]=4，A[5]=5，A[6]=-1，A[7]=2

函数应返回17，因为数组A的所有双切片的和的最大值为17。

假定：

1. N是区间[3，100000]内的整数；

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

• 解题思路

正向遍历数组，获得到达每个索引可以得到的最大值序列，然后反向获得到达每个索引的最大值序列，后者的最大值序列需要倒转。然后间隔一个位置，遍历这2个数组，最后取得到的最大值。

• Python3代码

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


def solution(A):
    """
    返回数组A的所有双切片中的和的最大值
    :param A: 数组
    :return: 返回双切片的和的最大值
    """
    length = len(A)
    if length == 3 or max(A) <= 0:
        return 0

    #  正向遍历
    forward_max = [0] * length
    for index, value in enumerate(A[1:-1]):
        forward_max[index + 1] = max(forward_max[index] + value, 0)

    reverse_max = [0] * length
    for index, value in enumerate(A[::-1][1:-1]):
        reverse_max[index + 1] = max(reverse_max[index] + value, 0)

    reverse_max = reverse_max[::-1]

    combine_max = []
    for i in range(1, length - 1):
        combine_max.append(forward_max[i - 1] + reverse_max[i + 1])
    return max(combine_max)

• 结果

image

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

image image