文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

python编写PAT 1007 Max

2023-01-31 00:23

关注

wenzongxiao1996
2019.4.3

题目

Given a sequence of K integers { N​1, N2, ..., N​K}. A continuous subsequence is defined to be { N​i, N​i+1, ..., N​j} where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4

暴力解法(超时了)

def seq_sum(s):
    """求序列的所有元素之和"""
    result = 0
    for i in range(len(s)):
        result += s[i]
    return result

def main():
    n = int(input())
    seq = [int(i) for i in input().split()]
    max = -1
    pos_i = 0
    pos_j = n-1
    for i in range(n):
        for j in range(i,n):
            sum_temp = seq_sum(seq[i:j+1])
            if sum_temp > max:
                max = sum_temp
                pos_i = i
                pos_j = j
    if max < 0:
        print(0,seq[pos_i],seq[pos_j])
    else:
        print(max,seq[pos_i],seq[pos_j])

if __name__ == '__main__':
    main()

分治法

def division_solution(seq,left,right):
    if left == right: # 递归出口
        if seq[left] >= 0:
            return left,right,seq[left]
        else:
            return left,right,-1
    center = (left+right)//2 # 地板除

    # 从中间到左边的最大子串
    sum_left = 0
    max_sum_left = -1  # 一定要设为负数
    pos_left = left   # 要返回下标
    for i in range(left,center+1)[::-1]:  # 反向迭代
        sum_left += seq[i]
        if sum_left >= max_sum_left:
            max_sum_left = sum_left
            pos_left = i

    # 从中间到右边的最大子串
    sum_right = 0
    max_sum_right = -1  # 一定要设为负数
    pos_right = right  # 要返回下标
    for i in range(center+1,right+1):
        sum_right += seq[i]
        if sum_right > max_sum_right:
            max_sum_right = sum_right
            pos_right = i

    # 递归求解左右两个子问题
    i_left,j_left,max_left_sum = division_solution(seq,left,center)
    i_right,j_right,max_right_sum = division_solution(seq,center+1,right)

    if max(max_left_sum,max_right_sum,max_sum_left+max_sum_right) < 0:
        return left,right,-1
    else:
        if max(max_left_sum,max_right_sum,max_sum_left+max_sum_right) == max_left_sum:
            return i_left,j_left,max_left_sum
        elif max(max_left_sum,max_right_sum,max_sum_left+max_sum_right) == max_right_sum:
            return i_right,j_right,max_right_sum
        else:
            return pos_left,pos_right,max_sum_left+max_sum_right


def main():
    n = int(input())
    seq = [eval(i) for i in input().split()]
    i,j,sum_max = division_solution(seq,0,n-1)
    if sum_max < 0:
        print(0,seq[0],seq[-1])
    else:
        print(sum_max,seq[i],seq[j])

if __name__ == '__main__':
    main()

动态规划

def main():
    n = int(input())
    seq = [eval(i) for i in input().split()]
    sum_max = -1
    pos_i = 0
    pos_i_temp = 0 # 最大子序列的左下标不能随意更改,只有找到了更大的子串才能改,用这个变量先保存着当前寻找的子串的左下标
    pos_j = n-1
    sum_temp = 0
    for i in range(n):
        sum_temp += seq[i]
        if sum_temp > sum_max:
            sum_max = sum_temp
            pos_j = i
            pos_i = pos_i_temp
        elif sum_temp < 0:# 和小于0的子串不需要考虑
            sum_temp = 0
            pos_i_temp = i+1
    if sum_max < 0:
        print(0,seq[0],seq[-1])
    else:
        print(sum_max,seq[pos_i],seq[pos_j])

if __name__ == '__main__':
    main()

谢谢观看!敬请指正!
参考博客:https://www.cnblogs.com/allzy/p/5162815.html
原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯