精华内容
下载资源
问答
  • 最大字段和问题

    2014-12-16 13:26:50
    求一个n个数的最大字段和问题,以及对其进行输出。基本的贪心算法问题。常用与研究生算法课程。
  • C++的作业,最大字段和问题 分治法,程序直接用dev就能运行。求一个序列的最大子段和即最大连续子序列之和。例如序列[4, -3, 5, -2, -1, 2, 6, -2]
  • 分治法求解最大字段和问题 1 问题描述  给定由n个整数(可能由负数)组成的序列(a1, a2,...,an),最大字段和问题求 该序列中连续子段和的最大值,并找出这个连续子段。 2 使用python编程解决,具体代码如下 ...

    分治法求解最大字段和问题

    1 问题描述

      给定由n个整数(可能由负数)组成的序列(a1, a2,...,an),最大字段和问题求 该序列中连续子段和的最大值,并找出这个连续子段。

    2 使用python编程解决,具体代码如下

     

    # 求出最大子段和, 以及最大子段和 对应的位置,返回的位置 可能时乱序,由于是连续的,找出最大值和最小值,即确定位置
    def max_sum(row_data, left, right):
        sum_max_sub = 0
        position_list = []
        if left == right:
            if row_data[left] > 0:
                sum_max_sub = row_data[left]
                position_list.append(left)  # 记录下位置
            else:
                sum_max_sub = 0
        else:     # 三种情况
            center = (left + right) // 2
            left_sum, left_position = max_sum(row_data, left, center)     # 左侧 连续子段最大和
            right_sum, right_position = max_sum(row_data, center+1, right)  # 右侧 连续子段最大和
    
            # 第三种情况, 从中间向两侧 的连续子段最大和
            s1 = 0  # 用来记录 子段和
            lefts = 0
            for i in range(center, left-1, -1):
                lefts += row_data[i]
                if lefts > s1:
                    s1 = lefts
                    position_list.append(i)
    
            s2 = 0  # 用来记录 子段和
            rights = 0
            for j in range(center+1, right+1):
                rights += row_data[j]
                if rights > s2:
                    s2 = rights    # 在这个 找位置吗??
                    position_list.append(j)
    
            sum_max_sub = s1 + s2
            if sum_max_sub < left_sum:
                sum_max_sub = left_sum
                position_list = left_position
            if sum_max_sub < right_sum:
                sum_max_sub = right_sum
                position_list = right_position
    
        print("最大字段和为:{}".format(sum_max_sub))
        print("最大字段和对应的索引:{}".format(position_list))
        return sum_max_sub, position_list
    
    
    def max_main():
        row_data = [-20, 11, -4, 13, -5, -2]
        max_sum(row_data, 0, len(row_data)-1)
    
    
    max_main()

     

    转载于:https://www.cnblogs.com/generalLi/p/9898540.html

    展开全文
  • 最大字段和问题:分别用蛮力法 分治法 动态规划法去实现的!是我交给老师的实验报告!!
  • 蛮力法求解最大字段和问题C++代码 以下代码实现了用蛮力法求解最大字段和问题,并统计代码运行时间 #include <iostream> #include <stdlib.h> #include <windows.h> #include <iomanip> #...

    蛮力法求解最大字段和问题C++代码

    以下代码实现了用蛮力法求解最大字段和问题,并统计代码运行时间

    #include <iostream>
    #include <stdlib.h>
    #include <windows.h>
    #include <iomanip>
    #include <stdio.h>
    
    using namespace std;
    
    int *maxSum(int a[], int len){
        int maxSum = 0;
        int sum = 0;
        int i, j, *index;
    
        index = (int *)malloc(sizeof(int)*3);   //申请空间
    
        for(i=0; i<len; i++){
            sum = a[i];
            for(j=i+1; j<len; j++){
                a[i]+=a[j];     //a[i]及后面所有元素的和
                if(a[i]>sum){
                    sum = a[i]; //每一趟的最大值
                    if(a[i]>maxSum){
                        index[2] = j+1;
                    }
                }
            }
    
            if(sum>maxSum){
                maxSum = sum;
                index[0] = sum;
                index[1] = i+1;
            }
        }
        return index;
    }
    int main()
    {
        int a[6] = {-20, 11, -4, 13, -5, -2};
        int *max;
    
        LARGE_INTEGER nFreq;
        LARGE_INTEGER nBeginTime;
        LARGE_INTEGER nEndTime;
        double time;
    
        QueryPerformanceFrequency(&nFreq);
        QueryPerformanceCounter(&nBeginTime);
    
        max = maxSum(a, 6);
    
        QueryPerformanceCounter(&nEndTime);
        time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)*1000000000/(double)(nFreq.QuadPart);
    
        cout << "最大子段和是:" << max[0] << endl;
        cout << "Start:" << max[1] << endl;
        cout << "End:" << max[2] << endl;
        cout << "Time used: " << time << endl;
        return 0;
    }
    
    展开全文
  • 如果你对动态规划方法求解最大字段和问题的思路不太清楚,直接阅读代码不是一个好的建议。 推荐一个讲解视频: 最大子序和 - 动态规划 练习网址(视频配套的练习) #include<iostream> using namespace std; ...

    如果你对动态规划方法求解最大字段和问题的思路不太清楚,直接阅读代码不是一个好的建议。

    推荐一个讲解视频:
    最大子序和 - 动态规划
    练习网址(视频配套的练习)

    #include<iostream>
    using namespace std;
    
    int maxSubArray(int a[], int length)
    {
        int final_max=a[0];
        for (int i = 1; i < length; i++)
        {
            if (a[i-1] > 0)//如果a[i-1]大于0,
            {
                a[i] += a[i-1];//那么就 a[i] = a[i] + a[i-1]
                final_max < a[i] ? final_max = a[i] : NULL; //如果 final_max 小于 a[i],就将 a[i] 赋给 final_max
            }
            else//如果 a[i-1] 小于0,
            {   
                final_max < a[i] ? final_max=a[i] : NULL;//如果 final_max 小于 a[i],就将 a[i] 赋给 final_max
            }
        }
        return final_max;
    }
    
    int main()
    {
        int a[] = {-14,-9,-6,-5,-15,8,5,10,-6};
        int length = sizeof(a)/sizeof(int);
        int result = maxSubArray(a, length);
        cout<<"最大字段和是:"<<result<<endl;
        return 0;
    }
    
    展开全文
  • 用动态规划法求解最大字段和问题,DEV C++环境运行,测试可用可进行多组数据测试
  • 基本题二:最大字段和问题 一、实验目的与要求 1、熟悉最长最大字段和问题的算法; 2、进一步掌握动态规划算法; 二、实验题 若给定n个整数组成的序列a1,a2,a3,...,an,求该序列形如ai+ai+1+...+an的...

     基本题二:最大字段和问题

     


    一、实验目的与要求


    1、熟悉最长最大字段和问题的算法;


    2、进一步掌握动态规划算法;


    二、实验题


        若给定n个整数组成的序列a1a2a3,...,an,求该序列形如aiai1+...+an的最大值。


    三、实验提示


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    int MaxSum(int n,int *a,int &besti,int &bestj)
    {
      int sum=0;
      for(int i=1;i<=n;i++)
      for(int j=i;j<=n;j++)
       {
         int thissum=0;
         for(int K=i;k<=j;k++)thissum+=a[k];
         if(thissum>sum)
           {
             sum=thissum;
             besti=i;
             bestj=j;
            }
         }
        return sum;
     }
    intMaxSum(int n,int *a,int &besti,int &bestj)
     {
       int sum=0;
       for(inti=1;i<=n;i++)
       {
         int thissum=0;
         for(intj=i;j<=n;j++)
          {
            thissum+=a[j];
            if(thissum>sum)
            {
              sum=thissum;
               besti=i;
               bestj=j;
              }
             }
        }
        return sum;
    }

     



     

    四、源代码


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public static void main(String[] args) {
            int[] a = { 128282910 };
            System.out.println(maxSum(3, a));
        }
     
        public static int maxSum(int n, int[] a) {
            int sum = 0;
            for (int i = 0; i < a.length - n + 1; i++) {
                int thissum = 0;
                for (int v = 0; v < n; v++) {
                    System.out.println(v + "--" + i);
                    thissum += a[v + i];
                }
                System.out.println("---------------------------" + thissum);
                if (thissum > sum)
                    sum = thissum;
     
            }
     
            return sum;
        }

    0--0

    1--0

    2--0

    ---------------------------22

    0--1

    1--1

    2--1

    ---------------------------18

    0--2

    1--2

    2--2

    ---------------------------12

    0--3

    1--3

    2--3

    ---------------------------19

    0--4

    1--4

    2--4

    ---------------------------21

    22


    本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/824843




    展开全文
  • 算法设计8-数列最大字段和问题 参考例题15,P143页 问题描述 代码 #include<iostream> using namespace std; int max_sum3(int a[],int n); int max_sub_sum(int a[],int left,int right) { //s1=a[i]+...+a...
  • 连续最大字段和问题

    2019-07-01 20:23:00
    最大子段和问题描述 ... 例如:当(a1,a2,a3,a4,a5)=(-2,11,-4,13,-5,-2)时,最大字段和为 20 (11 + (-4) + 13); 以下例子都是以int data[6] = {-2,11,-4,13,-5,-2}; int n = 6; ...
  • 最大字段和问题详解

    2020-05-06 09:20:19
    最大字段和求解 思路分析 代码实现 /*简单算法*/ int maxsize(int n,int *a,int& besti,int& bestj) { int sum=0,i,j,k; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int thissu...
  • ACM最大字段和问题

    2018-04-12 19:43:00
    HDU1003Max Sum题意:给n个数,求最大连续字段以及起始位置。状态转移方程:dp[i] = max(dp[i] + s[i], s[i]);理解起来就是以s[i]结尾的最大连续字段上一个状态只有两种:连续的,或者重新开始。代码:#include&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,387
精华内容 554
关键字:

最大字段和问题