做外贸网站需要什么条件,网站的icp是什么意思,wordpress slides,wordpress注册项牛客题霸 [子数组的最大累加和问题] C题解/答案
题目描述
给定一个数组arr#xff0c;返回子数组的最大累加和 例如#xff0c;arr [1, -2, 3, 5, -2, 6, -1]#xff0c;所有子数组中#xff0c;[3, 5, -2, 6]可以累加出最大的和12#xff0c;所以返回12. [要求] 时间复…牛客题霸 [子数组的最大累加和问题] C题解/答案
题目描述
给定一个数组arr返回子数组的最大累加和 例如arr [1, -2, 3, 5, -2, 6, -1]所有子数组中[3, 5, -2, 6]可以累加出最大的和12所以返回12. [要求] 时间复杂度为O(n)O(n)空间复杂度为O(1)O(1)
题解
我们从前向后推如果当前值加上前一个值小于当前值那我们就不加了如果大于我就加上这样维护的是每个位置所能累加的最大值我们在这个过程中用maxx取最大情况
代码
class Solution {
public:/*** max sum of the subarray* param arr int整型vector the array* return int整型*/int maxsumofSubarray(vectorint arr) {// write code hereint maxxarr[0];for(int i1;iarr.size();i){arr[i]max(arr[i],arr[i]arr[i-1]);maxxmax(arr[i],maxx);}return maxx;}
};
