|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-5-8 18:08 编辑
题目描述:
- 输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
- 要求时间复杂度为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.暂无。 |
|