连续日记的最佳片段

故事背景

小明坚持在日记本上记录自己每天的心情，用一个整数表示当天的“心情指数”：正数代表愉快，负数代表不太开心，数值越大代表情绪越好。

学期结束时，小明想从这本日记中，挑出一段连续的日子，作为自己这一学期“印象最美好的一段记忆”。他决定用这一段连续天数的心情指数之和，来衡量这段记忆的“美好程度”。

现在，小明把整学期的心情指数按时间顺序整理成了一串数字，希望你能帮他找到一段“总和最大”的连续日记片段。

题目描述

给定一个长度为 $n$ 的整数数组，表示按时间顺序记录的心情指数。请你找到一个连续子数组，使得该子数组所有元素之和最大，并输出这个最大和。子数组至少包含一个元素。

输入格式

• 第一行包含一个整数 $n$，表示天数。
• 第二行包含 $n$ 个整数，表示每天的心情指数。

输出格式

• 输出一行，一个整数，为和最大的连续子数组的和。

输入输出样例 #1

输入 #1

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

输出 #1

6

样例解释 #1

和最大的连续片段为 $[4, -1, 2, 1]$，它们的和为 $4 + (-1) + 2 + 1 = 6$。

说明/提示

• 对于所有测试数据，保证 $1 \le n \le 2 \times 10^5$。
• 每个心情指数的绝对值不超过 $10^9$。
• 请注意使用 64 位整数类型存储中间和结果。