HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int sum=0;
        int res=array[0];
        for (int i=0;i<array.length;i++){
            sum = sum + array[i];
            if(sum>res){
                res=sum;
            }
            if(sum<0){
                sum=0;
            }
        }
        return res;
    }
}

原文地址:https://www.cnblogs.com/q-1993/p/10871889.html

时间: 05-15

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会的相关文章

《团队开发一(求一个数组的连续的子数组之和的最大值)》

(1)设计思想:一般的,求一个数组的最大子数组之和即是按数组顺序依次让前几个数的和与下一个数进行比较,设一变量来装每次比较后的较大的数,依此进行到数组终端:但是考虑到求的是连续的子数组,则应该想到除了在按顺序上的连续外,还得考虑到末端与首端的连续,所以按数组顺序依次求解得到的未必就是连续的最大的子数组之和,故此必须在此种情况下也求解出最大子数组之和,方法即是同时从数组的两端依次进行求出各自的最大子数组之和,然后在相遇前求和后与之前所求的最大子数组之和依次相比较,取它们中最大的一个作为连续的最大子

找出一个整数数组的和最大的连续子数组

题目: 给任意一个整数数组,找出这个数组的和最大的连续子数组(子数组的和最大且子数组连续).要求:算法的时间复杂度为O(n). 程序设计思想: 1:用maxValue记录当前连续子数组和为最大的和的值,初始化其值为:maxValue=a[0].注:记数组为a[n]. 2:这个过程总的思想就是,从数组头开始往后,每次加进一个值,它们的和记为tempValue,若tempValue比新加进来的数值本身要小,应该从这个位置开始重新开始计算tempValue的值.而每次的tempValue都应该和max

算法题:找出一个数组中相加值最大的连续序列元素

package arithmetic; /** * @author SHI * 求一个数组中相加值最大的连续序列元素 */ public class MaxSequence { public static void main(String[] args) { int[] a=new int[]{-2,9,-3,4,-6,7,-6,4}; findBigSequence(a); } /** * 思想: (1)计算出该数组的所有元素和,假设该值为最大 * (2)从数组下标1到a.length-1依次

【转载】让c++ 函数返回一个数组

在c++中是不允许数组作为函数的返回值的 int [] someFunction( ); //ILLEGAL 要想实现函数返回一个数组,那返回对应数组里面类型的指针 you must return a pointer to the array base type and have the pointer point to the array. So, the function declaration would be as follows: int* someFunction( ); //Leg

求一个数组的子数组的最大和

如题:求一个数组的子数组的最大和,要求O(n)时间复杂度. 由于有了O(n)时间复杂度的限制,所以暴力求解的O(n^2)方法肯定不行.再考虑递归求一个数组a[n]的子数组的最大和,可以分解为a[i]子数组的最大和以及a[n-i-1]之间的某种情况 a[n]的子数组最大和等于a[i]子数组的最大和: a[n]的子数组最大和等于a[n-i-1]: a[n]的子数组最大和跨a[i]和a[n-i-1]: 递归实现的时间复杂度为O(nlg(n)).最后考虑时间复杂度为O(n)的动态规划实现. /** *

c++函数返回一个数组

---恢复内容开始--- 调用某个函数时经常需要函数返回一个值,我们都知道c++ 的函数返回的是一个copy,所以当只返回一个值时不会出现什么问题,直接return一个copy就行了,但是如果返回一个数组,事情就变得有趣了,我最近就遇到了这个问题. 先附上代码吧: #include<iostream> using namespace std; //函数声明 int * fun1(); int * fun2(); void dispArr(int *arr ,int n); const int

《返回一个数组的最大值》

设计思想:手动或使用随机函数生成一系列数组成一个数组,设计求数组中最大值的函数,在主函数中调用即可:但是考虑到用户的各种需求与程序的各种不一致性,为此设计了相关的能柔和两种状态下的各种情况测试提醒: (1)计算机会对用户有意无意输入的数组长度为0,复数,或大于分配的内存空间情况而对用户做不了用户满意的应答,故在程序中加一段对用户输入的数组长度判断的测试,则用户便可根据系统的提示一步步进行即可. (2)由于用户的无意性,可能会混淆键入不同的数据类型,然而计算机并不能愉快的解决此问题为用户得来满意的

给出一个数组A,找出一对 (i, j)使得A[i] &lt;= A[j] (i &lt; j)并且j-i最大

题目:给出一个数组A,找出一对 (i, j)使得A[i] <= A[j] (i <= j)并且j-i最大 ,若有多个这样的位置对,返回i最小的那一对. 最直接的想法就是对于每一个 i 从数组最尾端开始向前找到第一个大于等于 A[i] 的位置 j ,时间复杂度O(n^2). 1. pair<int, int> find(const vector<int> &A) 2. { 3. int n = A.size(); 4. if(n == 0) 5. throw ne

转---网络上来的,做一个数组样的结构

SQL分割字符串仿造数组 程序一:create function [dbo].[GF_StringSplit] (@str nvarchar(max), --字符串 @spliter nvarchar(10)) --分割符 returns @tb table(ch nvarchar(256)) --返回对应表 AS BEGIN DECLARE @Num int,@Pos int, @NextPos int SET @Num = 0 SET @Pos = 1 WHILE(@Pos <= LEN(@

LeetCode:Find Peak Element - 寻找一个数组内的顶点

1.题目名称 Find Peak Element(寻找一个数组内的顶点) 2.题目地址 https://leetcode.com/problems/find-peak-element/ 3.题目内容 英文: A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its