豕の家

留住 温度 速度 温柔和愤怒

算法  连续子数组的最大和
March 11, 2021 / 15:22 / 49 °C

ysg.gif

JS教程后的一道习题,CPP写也一样。

/*
输入是以数字组成的数组,例如 arr = [1, -2, 3, 4, -9, 6].
任务是:找出所有项的和最大的 arr 数组的连续子数组。
写出函数 getMaxSubSum(arr),用其找出并返回最大和。
例如:
getMaxSubSum([-1, 2, 3, -9]) == 5(高亮项的加和)
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6(所有项的和)
如果所有项都是负数,那就一个项也不取(子数组是空的),所以返回的是 0:
getMaxSubSum([-1, -2, -3]) = 0
*/

#include<iostream>
using namespace std;
//O(n^2)的暴力解法,对每一种可能的连续子数组都进行对比
int getMaxSubSum(int n,int* a){
    int max;
    for(int i=0;i<n;i++){
        int s=0;
        for(int j=i;j<n;j++){
            s+=a[j];
            if(s>max) max=s;
        }
    }
    return max;
} 

//O(n)的解法
int getMaxSubSum_o(int n,int *a){
    int max=0,sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(sum>max) max=sum;
        //当sum变成负数的时候会拖累后面的累加
        //所以直接重置,从下一个开始寻找最大和的连续子数组
        if(sum<0) sum=0;
    }
    return max;
}

int main(){
    int a[]={-1, -2, -3};
    cout<<getMaxSubSum(3,a)<<endl;
    cout<<getMaxSubSum_o(3,a)<<endl;
    int b[]={-1, 2, 3, -9, 11};
    cout<<getMaxSubSum(5,b)<<endl;
    cout<<getMaxSubSum_o(5,b)<<endl;
    int c[]={100, -9, 2, -3, 5};
    cout<<getMaxSubSum(5,c)<<endl;
    cout<<getMaxSubSum_o(5,c)<<endl;
    int d[]={2, -1, 2, 3, -9};
    cout<<getMaxSubSum(5,d)<<endl;
    cout<<getMaxSubSum_o(5,d)<<endl;
    return 0;
}

对于题目的特殊约束:当所有数组项都为负数的时候最大值取0,如果要推广到一般情况,只需要把max=0的初始化条件改为max=a[0]即可。





© Posted By @shawnt

Comment

称呼:  
邮箱:  
网址: