• 中文
    • English
  • 注册
  • 查看作者
  • 浙江大学MOOC——数据结构:最大子列和问题

    一.  前言

    今天开始跟着浙江大学MOOC学习数据结构

    以后以浙江大学MOOC–数据结构的前缀发表该课程下的所有练习题整理答案

    分别用C++和Java实现

    二.  最大子列和问题

    2.1  题目要求

    浙江大学MOOC——数据结构:最大子列和问题

    2.2  解题思路

    采用在线处理法,将算法的复杂度降为T(N) = O(N)

    在线是指每输入一个数据就进行及时处理,在任何一个地方终止输入,都不会影响正确性

    首先将序列中的元素从左向右累加

    发现更大的累加和就更新当前最大值

    若累加和小于0,便抛弃之,从0开始重新累加

    因为若累加和小于0,不可能使后面的累加和增大

    2.3  C++实现

    #include <iostream>
    using namespace std;
    int Max(int n,int a[])
    {
        int ThisSum,MaxSum;
        ThisSum = MaxSum = 0;
        for (int i = 0; i < n; i++)
        {
            ThisSum += a[i];//向右累加和
            if(ThisSum > MaxSum)
            {
                MaxSum = ThisSum;//发现更大的和,则更新当前的最大值
            }
            else if(ThisSum < 0)
            {
                ThisSum  = 0 ;//如果当前子列和为负,则重新赋值为0,
            }
    
        }
        return MaxSum;
    }
    int main()
    {
        int n;
        cin>>n;
        int *a=new int[n];
    
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        cout<<Max(n,a);
        delete []a;
        return 0;
    }

    2.4  Java实现

    package cn.pintia;
    
    import java.util.Scanner;
    
    public class Test {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		int a[] = new int[n];
    		for (int i = 0; i < n; i++) {
    			a[i] = input.nextInt();
    		}
    		System.out.println(Max(n,a));
    	}
    
    	public static int Max(int n, int a[]) {
    		int ThisMax,SumMax;
    		ThisMax = SumMax = 0;
    		for(int i = 0; i < n; i++) {
    			ThisMax += a[i];
    			if(ThisMax > SumMax) {
    				SumMax = ThisMax;
    			} else if(ThisMax < 0) {
    				ThisMax = 0;
    			}
    		}
    		return SumMax;
    		
    	}
    }
  • 0
  • 2
  • 0
  • 4.2k
  • 小可zjmarina

    请登录之后再进行评论

    登录
  • 0
    打赏了774金币。
  • 0
    6666666
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    单栏布局 侧栏位置: