精华内容
下载资源
问答
  • 求数组连续子序列最大和

    千次阅读 2018-05-04 09:30:53
     一整数数组L,如 L=[2,-3,3,50], L的一连续子序列,使其和最大,输出最大子序列的。这里非连续子序列的定义是,子序列中任意相邻的两数在原序列里都不相邻。例如,对于L=[2,-3,3,50], 输出52(分析:...

    题目描述:

    1. 一个整数数组L, L=[2,-3,3,50], L的一个非连续子序列,使其和最大,输出最大子序列的和。这里非连续子序列的定义是,子序列中任意相邻的两个数在原序列里都不相邻。例如,对于L=[2,-3,3,50], 输出52分析:很明显,该列表最大非连续子序列为[2,50])。测试例子:L=[-2,-3,3,50,1,-1,100]

    用动态规划的思想:

    public class MaxSubSum {
        
        public static int maxSubSum(int[] a) {
           a[1] = Math.max(a[1],a[0]);
           for (int i = 2; i < a.length; i++) {
                a[i]= Math.max(Math.max(a[i],a[i-1]),a[i-2]+a[i]);
            }
            return a[a.length-1];
        }
        public static void main(String[] args) {
            int [] a= {2,-3,3,50};
            int [] b= {-2,-3,3,50,1,-1,100};
            int result_a = maxSubSum(a);
            int result_b = maxSubSum(b);
            System.out.println(result_a);
            System.out.println(result_b);
        }
    }
    

    展开全文
  •  直接两for循环枚举子序列的首尾,然后再来循环计算序列,每次更新最大值。  但是这种方法的复杂度是O(n^3),效率实在太低了。。。 ————————————————————————————...

    1.首先最朴素的方法是暴力 O(n^3)

           直接两个for循环枚举子序列的首尾,然后再来个循环计算序列的和,每次更新和的最大值。

            但是这种方法的复杂度是O(n^3),效率实在太低了。。。

    ————————————————————————————————————————————————

    2. 第二种方法是预处理 O(n^2)

           在读入的时候将前面数的和放在数组中,就能得到一个数组sum[i]储存前i个数的和。然后两重循环枚举首尾,利用sum数组迅速求出子序列的和。

            其实这种方法只是优化了前面那种方法的计算和的循环,复杂的是O(n^2),也很糟糕。

    3. 第三种是动态规划 O(n)

            dp做法是很普遍的做法,只要想出状态转移方程就可以很快做出来了。

            状态转移方程:sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大连续和。)在dp的过程中便可以更新sum数组的最大值以及两个边界。

            其实完全可以不用开数组,累计sum直到sum + a < a,把sum赋值为a,更新最大值就行了。你会发现这跟第4种方法是一样的。。。只是判断条件不一样,一个是sum <= 0一个是sum + a < a。。。(其实是一样的。。。)所以复杂度和第四种是一样的都是O(n)。

    /* 最大子数组 返回起始位置 */
    <pre name="code" class="cpp">void Maxsum_location(int * arr, int size, int & start, int & end)
    {
        int maxSum = -INF;
        int sum = 0;
        int curstart = start = 0;  /* curstart记录每次当前起始位置 */
        for(int i = 0; i < size; ++i)
        {
            if(sum < 0)
            {
                sum = arr[i];
                curstart = i;     /* 记录当前的起始位置 */
            }else
            {
                sum += arr[i];
            }
            if(sum > maxSum)
            {
                maxSum = sum;
                start = curstart; /* 记录并更新最大子数组起始位置 */
                end = i;
            }
        }
    }

    
    
    另外一种方法求起始位置

    void Maxsum_location(int * arr, int size, int & start, int & end)
    {
        int maxSum = -INF;
        int sum = 0;
        for(int i = 0; i < size; ++i)
        {
            if(sum < 0){
                sum = arr[i];
            }else{
                sum += arr[i];
            }
            if(sum > maxSum)
            {
                maxSum = sum;
                end = i;//结束位置
            }
        }
         int tmp=0;int f=0;
         for(int j=end;j>0;j--)
         {
              tmp+=arr[j];
              if(tmp==maxSum)
                     f=j;//起始位置
          }
    }




    展开全文
  • 求数组最大连续子序列

    千次阅读 2018-08-06 21:06:54
    HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的...个数组,返回它的最大连续子序列,你会...

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

    笨办法:

    public class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {
            int ans = Integer.MIN_VALUE;
            for(int i=1; i<array.length+1; i++){
                if(array.length - i >0){
                    for(int j=0; j<array.length-i; j++){
                        int sum = 0;
                        for(int k = j; k<j+i; k++){
                            sum += array[k];
                        }
                        if(sum>ans)
                            ans = sum;
                    }
                }else{
                    int sum = 0;
                    for(int j = 0; j<array.length; j++){
                        sum += array[j];
                    }
                    if(sum >ans)
                        ans = sum;
                }
            }
            return ans;
        }
    }

    学习的办法:

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

     

    展开全文
  • 求数组连续子序列和最大

    千次阅读 2019-04-08 09:05:48
    转载出处:... 最好的算法就是利用动态规划来计算(DP[i] = max{DP[i-1] + A[i],A[i]}) class Solution { public: int getMaxSubSerial(int arr[],int size) { int ...

    转载出处:https://www.cnblogs.com/allzy/p/5162815.html(解释的非常透彻)

    最好的算法就是利用动态规划来计算(DP[i] = max{DP[i-1] + A[i],A[i]})

    class Solution {
    public:
        int getMaxSubSerial(int arr[],int size)
        {
            int MaxSum=0xf0000000;
            int AddSum=0;
            for(int i=0;i<size;++i)
            {
                if(AddSum<0)
                    AddSum=arr[i];
                else
                    AddSum+=arr[i];
                if(AddSum>MaxSum)
                    MaxSum=AddSum;
            }
            return MaxSum;
        }
    };

     

    展开全文
  •  1 遍历数组,如果当前累加小于 0 就让等于0;否则就保留最大的当前累加 int maxSubArray(int A[], int n) { int sum=0; if(n==0) return sum; int maxSum=A[0]; for(int i=0;i;i++){
  • 编程之美上的一题:出一整数序列S,其中有N数,定义其中一非空连续子序列T中所有数的为T的“序列”。对于S的所有非空连续子序列T,求最大的序列。 思路 * 数组第一元素A[0]和最大数组和...
  • 求数组最大连续子序列和

    千次阅读 2009-10-18 07:19:00
    求数组最大连续子序列和 问题:给定一整数数组a[n],在这个数组中和最大的一个连续子序列。分析:如果已经知道在前0~k-1共k元素中,在最大和为MaxAll[k-1], 怎么0~k共k+1元素的MaxAll[k]。 如果前k...
  • //只是一例子 int max=FindMaxSubSeq( A,0,5); printf("%d",max); return 0; } int FindMaxCrossSum(int A[],int left,int right) { int mid=(left+right)/2; int leftmax=-9999,leftsum=0; for(int i=mid;i>...
  • 给定一个数组,其中元素可正可负,其中最大连续子序列。 代码 public class FindGreatestSum { public static void main(String[] args) { int[] array = {6,-3,-2,7,-15,1,2,2}; System.out.println...
  • 看书、思考、写代码! /*************************************** ... * 题目:分治法求数组最大连续子序列和 * 思路:分解成子问题+合并答案 * 时间复杂度:O(n lgn) * 空间复杂度:O(1) ********
  • 求数组最大连续子序列和 1.数组长度至少是1: 当数组长度1 直接返回数组0元素 当i=1时 cur与max都为0元素 从1开始 当cur+array[1]>array[1]的时候(arr[0]+array[1]>array[1])cur为两数的 否则cur...
  • 给定一个数组,其中元素可正可负,其中最大连续子序列。 解题思路 本题需要的结果是一和数,所以我们应该创建一变量num用于保存这值。对于本题来说,若想得到最大的子序列,则在一连续区间内,若碰到...
  • 在这里插入代码片class Solution { public: int maxSubArray(vector<int>& nums) { int i,j,k=nums[0],sum=nums[0]; if(nums.size()==0) return nums[0]; for(i=1;i<...
  • 面试算法题:个数组最大子序列,就是求数组连续的值的求最大值。
  • 数组最大连续子序列和问题,是一较为“古老”的一问题。该问题的描述为,给定一整型数组(当然浮点型也是可以的啦),取其下标连续的子序列,且其为该数组的所有子序列中值为最大的。例如数组A={1...
  • 连续子序列最大和,其实就是序列中连续的子序列中元素最大的那个。 比如例如给定序列: { -5,-2, 11, -4, 13, -5, -8 } 其最大连续子序列为{ 11, -4, 13 },最大为20。 方法一:暴力 O(n^3) 算法描述...
  • 求数组最大连续子序列和的四种算法 // 求数组最大连续子序列和 // 2017/8/3 #include int MaxSubsequenceSum1(int a[], int n); int MaxSubsequenceSum2(int a[], int n); int MaxSubsequenceSum3(int a[],...
  • 首尾相连数组最大子序列和

    千次阅读 2014-03-19 20:49:00
    数组中一或多连续元素可以组成一数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这ACM_Lover用一最高效的方法帮忙找出所有连续子数组和最大值(如果数组中的元素全部为负数
  • 数组 求连续子序列最大和程序 时间复杂度O(n) 空间复杂度O(1)
  • var array=[1, -2, 3, 10, -4, 7, 2, -5]; //结果为3, 10, -4, 7, 2 alert(findSubArray(array).join(",")); function findSubArray(array){ ... result[0]="数组为空!";  return resu
  • 求数组最大子序列和

    千次阅读 2013-03-17 21:13:02
     数组连续的一个或多个整数组成一个子数组,每个子数组都有一个和。  所有子数组的和的最大值。要求时间复杂度为O(n)。  例如:输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大子数组为3, 10, -4, 7, ...
  • 整型数组中的最大连续子序列和,例如数组(3,2,-1,4,-3)中和最大的连续子序列为(2,-1,4),其为5。 Java代码如下: public class Main { public static void main(String args[]) { int[] arr = {...
  • 数组连续子序列最大和&最大

    千次阅读 2013-10-14 21:52:27
    int MaxProduct(int* arr, int len) { int dp1 = arr[0]; int dp2 = arr[0]; int largest = arr[0]; for (int i = 1; i ; ++i) { int tmp1 = dp1*arr[i]; int tmp2 = dp2*arr
  • python循环数组连续子数组最大和问题的求解思路如下: 正常数组中间的某一段和最大。这可以通过普通的最大子段问题出。 此数组首尾相接的某一段和最大。这种情况是由于数组中间某段为负值,且...
  • 计算一个数组最大子序列

    千次阅读 2012-10-08 15:43:42
    数组连续的一个或多个整数组成一个子数组,每个子数组都有一个和。  所有子数组的和的最大值。要求时间复杂度为 O(n)。 int arr[10]; void randData(int a[], int start, int end) { srand(time(NULL)); ...
  • 题目描述: ...S(i)为以array[i]结尾时,最大连续子序列 S(i+1)=max(array[i],S(i)+array(i)) res为以array[i]结尾时,整个过程中最大子序列的 res=max(res,S(i+1)) 故实现代码为: class Solution:...
  • 个数组连续子数组最大值(以及区间) package suanfa.impover; /** * 个数组连续子数组最大值(以及区间) */ import java.util.Arrays; public class SubArrayMaxSum { // 暴力破解,O(n2)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,435
精华内容 20,974
关键字:

给个数组求连续子序列最大和