如何在C++中降低这个解决方案的时间复杂性？

Question

给定一个整数数组nums，查找具有最大和的相邻子数组（至少包含一个数字）并返回其和。

示例：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        
        int max=INT_MIN;
        int result;
        int i,j;
        if(nums.size()==1)
            return nums[0];
        if(nums.size()==0)
            return 0;
        for(i=0;i<nums.size();i++)
        {
            
            for(j=i;j<nums.size();j++)
            {
                
                result=accumulate(nums.begin()+i,nums.begin()+j+1,0);
                if(result>max)
                    max=result;
                
            }
            
        }
        return max;
    }
};

Answer 1

这可以使用Kadane的算法。

#include<algorithm> //this header file is required for max function.
class Solution
{
public:
    int maxSubArray(vector<int>& nums) {
        int temp=0;
        int max_sum=0;
        for(int i=0;i<nums.size();i++)
        {
            temp=max(temp+nums[i],nums[i]);
            max_sum=max(temp,max_sum);
        }
        return max_sum;
    }
};