A. 【入门】最大子数组和

传统题

100ms

32MiB

题目描述

给你一个整数数组 a ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

第一行一个整数 $n$ ，表示数的个数，( $1 \le n \le 10^5$ )

第二行有 $n$ 个整数， $a_i$ 表示第 $i$ 个数 ( $-10^4 \le a_i \le 10^4$ )。

一个整数，表示最大子数组和

9
-2 1 -3 4 -1 2 1 -5 4

1
-1

-1

5
5 4 -1 7 8

样例 1 的最大子数组是 [4,-1,2,1]
样例 3 的最大子数组是 [5,4,-1,7,8]
我们用 $ans[i]$ $an s [i]$ 表示以 $a[i]$ $a [i]$ 结尾的最大子数组和
- 第一种情况： $ans[i]=a[i]$ (不需要 $i$ 前面的数)
- 第二种情况： $ans[i]=ans[i-1]+a[i]$ （ $a[i]$ 加上以 $a[i-1]$ 结尾的最大子数组）
最后的记过就是 $ans[0...n-1]$ 中的最大值