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

一.  前言

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

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

分别用C++和Java实现

二.  最大子列和问题

2.1  题目要求

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;
		
	}
}