最大连续数列和 牛客网 程序员面试金典 C++ Python
题目描述
对于一个有正有负的整数数组,请找出总和最大的连续数列。
给定一个int数组A和数组大小n,请返回最大的连续数列的和。保证n的大小小于等于3000。
测试样例:
[1,2,3,-6,1]
返回:6
C++
class MaxSum { public: //run:6ms memory:488k int getMaxSum(vector<int> A, int n) { int MaxSum = A[0]; int ThisSum = 0; for (int i =0; i<n;i++){ ThisSum += A[i]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if(ThisSum < 0) ThisSum = 0; } return MaxSum; } };Python
class MaxSum: #run:70ms memory:5732k def getMaxSum(self, A, n): MaxSum = A[0] ThisSum = 0 for i in range(n): ThisSum += A[i] if ThisSum > MaxSum: MaxSum = ThisSum elif ThisSum < 0: ThisSum = 0 return MaxSum
转载于:https://www.cnblogs.com/vercont/p/10210318.html
相关资源:JAVA上百实例源码以及开源项目