计算机导论 (2021年秋) 编程练习

[-2,1,-3,4,-1,2,1,-5,4]

6

[1]

1

[5,4,-1,7,8]

23

提示

• 你应该使用动态规划的思想: 将一个复杂问题拆解为简单的子问题, 进而求解.
• 对于这道题目, 以输入[5,4,-1,7,8]为例, 你可以将问题逐步拆解为:
  • 以8结尾的连续子数组的最大和是多少；
  • 以7结尾的连续子数组的最大和是多少；
  • 以-1结尾的连续子数组的最大和是多少；
  • 以4结尾的连续子数组的最大和是多少；
  • 以5结尾的连续子数组的最大和是多少；
• 然后就可以就可以逐步求解了:
  • 以5结尾的连续子数组的最大和是5;
  • 以4结尾的连续子数组的最大和是9;
  • 以-1结尾的连续子数组的最大和是8;
  • 以7结尾的连续子数组的最大和是15;
  • 以8结尾的连续子数组的最大和是23;
• 也即:
  • 以arr[i]结尾的连续子数组的最大和为 以arr[i-1]结尾的的最大和 + x 和 x 之间的较大值
  • 数组arr[0:n]的最大子数组和为 从0到n中,以arr[i]结尾的连续子数组最大和 中的最大值.

数据输入输出部分已为你准备好, 请书写函数体部分以完成作答.

def maxSubArray(nums) -> int:
    # finish the function.

    return maxAns

nums = [int(x) for x in input().strip('[]').split(',') if x] 
print(maxSubArray(nums))

题目来源: leetcode