T1.连续天数的最高利润额(100分) - 华为机试真题题解

考试平台： 时习知

分值： 100分（第一题）

考试时间： 两小时（共3题）

题目描述

公司每日盈利的利润额记于整数数组 profit，请返回连续一或多天利润额总和的最高值。

输入

第一行为一个整数，表示天数

第二行为整数列表，分别为每日的利润。

输出

输出整数，表示连续天数利润额总和的最高值。

示例1

输入：
4
2 3 -5 4

输出：
5

解释： 
"2 3”连续2天的利润总额总和为最高值，连续利润额为5。

示例2

输入：
5
7 5 -7 8 -1

输出：
13

解释： 
“7 5 -7 8”连续4天的利润总额总和为最高值，连续利润额为13。

题解

这个代码使用了动态规划的思想来解决问题。

它的解题思路是计算出利润数组的前缀和数组，然后通过比较当前元素与之前最小的前缀和的差值来更新最大利润。

• 时间复杂度：该算法只需要遍历一次利润数组，因此时间复杂度为 O(n)，其中 n 是利润数组的长度。
• 空间复杂度：需要额外 O(n) 的空间来存储前缀和数组和其他变量，因此空间复杂度也为 O(n)。

C++

#include <bits/stdc++.h>

using namespace std;

int maxProfit(vector<int>& profit)
{