最大连续数列和牛客网程序员面试金典 C++ Python

2024-09-07 15:05:14

最大连续数列和牛客网程序员面试金典 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

最新文章

热门文章