PATtest1.3:最大子列和

题目源于：https://pintia.cn/problem-sets/16/problems/663

题目要求：输入一个数列，求其最大子列和。

问题反馈：1.部分C++代码不是很熟练

2.没有仔细读清楚题目，原文已经说过小于零的情况，不用过多的思考

解决方法：1.打印课上的常见代码，记忆背诵并默写

2.写题之前，先读题。多读英文的题，习惯英文读题

自己写的代码：

#include<stdio.h>
//using namespace std
#define MAXN 100000

void maxsub(int b[], int m){
    int sumtem = , maxsum = -;
    int c = , d = m-,begin=;
    int j=;
    for ( j = ; j<m; j++){
        sumtem += b[j];
        if (sumtem>maxsum){
            maxsum = sumtem;
            begin=c;
            d = j;
        }
        else if (sumtem<)
        {
            sumtem = ;
            c = j+;

        }

    }
    int k=;
    for(j = ; j<m; j++){
        if(b[j]<) k++;
    }
    if(k==m){
        maxsum=b[];
    for(j = ; j<m; j++){
        if(b[j]>=maxsum) {
        maxsum=b[j];
        begin=j;
        d=j;
}    }

    }

    printf(" sum:%d   first:%d   last: %d ", maxsum, b[begin], b[d]);
}

int main(void){
    int k;
    scanf("%d", &k);
    int a[MAXN] = {  };
    int i = ;
        for (i = ; i<k; i++){
            scanf("%d", &a[i]);
        }
    maxsub(a, k);
    return ;
}

优秀的网页代码：

#include "stdafx.h"
#include<iostream>
#include <vector>
using namespace std;

int main()
{
    int N;                //输入数列长度
    cin >> N;
    int * array = new int[N];
    for (int i = ; i < N; i++) {
        cin >> array[i];
    }
    //sum为子列和，MAX为最大子列和，first记录子列和的第一项，src为最大子列和的第一项，end为最大子列和的最后一项
    int sum=,first=,src=N-,end=N-,max=-;
    //动态规划
    for (int i = ; i < N; i++) {
        sum += array[i];
        //当前子列和>最大子列和时修改MAX,即SUM>MAX时，将max = sum.
        if (sum > max) {
            max = sum;
            src = first;
            end = i;
        }
        //sum<0时重置sum,first
        if (sum <) {
            first = i + ;
            sum = ;
        }
    }
    if (max<) cout <<  << ' ' << array[] << ' ' << array[N - ];
    else cout << max << ' ' << array[src] << ' ' << array[end];
    delete[] array;
    return ;
}

---------------------
作者：yzh1994414
来源：****
原文：https://blog.****.net/yzh1994414/article/details/78070888
版权声明：本文为博主原创文章，转载请附上博文链接！