鱼C论坛

 找回密码
 立即注册
查看: 1951|回复: 1

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

[复制链接]
发表于 2020-3-30 13:12:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-5-8 18:08 编辑

题目描述:
  1. 输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

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

  3.  

  4. 示例1:

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

  9. 提示:

  10. 1 <=&#160;arr.length <= 10^5
  11. -100 <= arr[i] <= 100

  12. 来源:力扣(LeetCode)
  13. 链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
  14. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. #include <vector>
  2. #include <iostream>

  3. using namespace std;

  4. int solution(vector<int>& nums){
  5.         int res;
  6.         int temp = 0;

  7.         for(int i = 0; i < nums.size(); i++){
  8.                 temp += nums[i];
  9.                        res = temp > res ? temp : res;
  10.                 for(int j = i + 1; j < nums.size(); j++){
  11.                         temp += nums[j];
  12.                         res = temp > res ? temp : res;
  13.                         //cout << res << endl;
  14.                         //cout << "----" << endl;
  15.                         if(temp <= 0){
  16.                                 break;
  17.                         }       
  18.                 }       
  19.                 temp = 0;
  20.         }
  21.        
  22.         return res;

  23. }


  24. int main(void){
  25.         cout << "please send numbers for the vector" << endl;
  26.         vector<int> input;
  27.         int number;
  28.         while(cin >> number){
  29.                 input.push_back(number);
  30.         }
  31.         int result = solution(input);
  32.         cout << result << endl;

  33.         return 0;
  34. }
复制代码



注意事项:
1.暂无。

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-3-31 12:44:21 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-7 11:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表