lintcode402. 连续子数组求和

末蓝、 2023-07-04 06:14 2阅读 0赞

给定一个整数数组，请找出一个连续子数组，使得该子数组的和最大。输出答案时，请分别返回第一个数字和最后一个数字的下标。（如果存在多个答案，请返回字典序最小的）

样例
    样例 1:
    
    输入: [-3, 1, 3, -3, 4]
    输出: [1, 4]
    样例 2:
    
    输入: [0, 1, 0, 1]
    输出: [0, 3]
    解释: 字典序最小.

class Solution {
        
    public:
        /*
         * @param A: An integer array
         * @return: A list of integers includes the index of the first number and the index of the last number
         */
        vector<int> continuousSubarraySum(vector<int> &A) {
        
            // write your code here
            vector<int>res(2,0);
            int start=0;
            int end=0;
            int sum=0;
            int maxs=INT_MIN;
            for (int i = 0; i < A.size(); i++) {
        
                /* code */
                if(sum<0)
                {
        
                    sum=A[i];
                    start=i;
                    end=i;
                }
                else
                {
        
                    sum+=A[i];
                    end=i;
                }
                if(sum>maxs)
                {
        
                    maxs=sum;
                    res[0]=start;
                    res[1]=end;
                }    
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode402. 连续子数组求和

给定一个整数数组，请找出一个连续子数组，使得该子数组的和最大。输出答案时，请分别返回第一个数字和最后一个数字的下标。（如果存在多个答案，请返回字典序最小的）样例

末蓝、/ 2023年07月04日 06:14/ 0 赞/ 3 阅读

相关 LintCode 41. 最大子数组

（一）题目描述给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。（二）样例样例1: 输入： \[−2,2,−3,4,−1,2,1,−5,3\

红太狼/ 2023年05月30日 10:47/ 0 赞/ 1 阅读

相关算法-分割数组为连续子序列

算法-分割数组为连续子序列 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/split-array-into

Bertha 。/ 2022年12月26日 10:13/ 0 赞/ 132 阅读

相关连续子数组最大和问题

1. 问题描述输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x ![132021534183635.png][] 应该返回 x\[2..6\]的和1

冷不防/ 2022年07月18日 01:12/ 0 赞/ 202 阅读

相关【lintcode】最大子数组

题目描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。子数组最少包含一个数样例给出数组[−2,2,−3

￡神魔★判官ぃ/ 2022年06月02日 21:08/ 0 赞/ 190 阅读

相关【LintCode 简单】41. 最大子数组

1.问题描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。注意事项子数组最少包含一个数 2.样例：给出数组`[−2,2,−3,

左手的ㄟ右手/ 2022年06月01日 04:07/ 0 赞/ 177 阅读

相关【LintCode 简单】138. 子数组之和

1.问题描述：给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 2.样例：给出 `[-3, 1, 2, -3, 4]

ゞ浴缸里的玫瑰/ 2022年06月01日 00:10/ 0 赞/ 195 阅读

相关 [LintCode] Continuous Subarray Sum 连续子数组之和

Given an integer array, find a continuous subarray where the sum of numbers is the bigge

短命女/ 2022年02月01日 09:15/ 0 赞/ 180 阅读

相关最短无序连续子数组

题目描述给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。示例

桃扇骨/ 2022年01月25日 16:09/ 0 赞/ 281 阅读

相关 LintCode : Dices Sum 骰子求和

试题： Throw n dices, the sum of the dices’ faces is S. Given n, find the all possible va

悠悠/ 2021年06月24日 16:10/ 0 赞/ 461 阅读