C++刷剑指offer(面试题42. 连续子数组的最大和)【数据结构】

糖逗

题目描述：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

 

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int>& nums){
        int res;
        int temp = 0;

        for(int i = 0; i < nums.size(); i++){
                temp += nums[i];
                       res = temp > res ? temp : res; 
                for(int j = i + 1; j < nums.size(); j++){
                        temp += nums[j];
                        res = temp > res ? temp : res; 
                        //cout << res << endl;
                        //cout << "----" << endl;
                        if(temp <= 0){
                                break;
                        }        
                }        
                temp = 0;
        }
        
        return res;

} 


int main(void){
        cout << "please send numbers for the vector" << endl;
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        int result = solution(input);
        cout << result << endl;

        return 0;
}

注意事项：
1.暂无。

糖逗