• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

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

    • 查看作者
    • 浙江大学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;
      		
      	}
      }
    • 2
    • 2
    • 0
    • 3.6k
    • 小可zjmarina

      请登录之后再进行评论

      登录
    • 0
      打赏了774金币。
    • 0
      6666666
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: