力扣1732. 找到最高海拔（前缀和）

本文主要是介绍力扣1732. 找到最高海拔（前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 1732. 找到最高海拔

题目描述

思路及解法

1.求取数组gain的大小$n$;
2.定义一个大小为$n+1$的数组preSum;
3.先求取前$n$个元素的前缀和，再最后单独处理preSum[n];其中preSum[n] = preSum[n - 1] + gain[n - 1];
4.求取处preSum中的最大元素；

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution {
public:/*** Prefix sum* * @param gain Given array* @return int*/int largestAltitude(vector<int>& gain) {int n = gain.size();vector<int> preSum(n + 1);int curSum = 0;for (int i = 0; i < n; ++i) {preSum[i] = curSum;curSum += gain[i];}preSum[n] = preSum[n - 1] + gain[n - 1];int maxRes = INT_MIN;for (int i = 0; i < n + 1; ++i) {maxRes = max(maxRes, preSum[i]);}return maxRes;}
};

这篇关于力扣1732. 找到最高海拔（前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---