每日一题之最大子段和

给定由n个整数组成的序列a1，a2，…，an，序列中可能有负数,
要在这n个数中选取相邻的子段ai，ai＋1，…，aj（1≤i≤j≤n），使其和最大，并输出最大的和。
例如:当{a1，a2，…，an}＝{1，-3，7，8，-4，12，-10，6}时，最大子段和为：sum＝23。
输入格式：第一行输入一个正整数N，表示序列的长度。N≤100000;第2行输入N个整数
输出格式：输出一个整数代表最大子段和 

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100000;
int main(){
long long a[N];
long long prefix[N];
long long n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
prefix[0]=a[0];
long long maxnum=a[0];
for(int i=1;i<n;i++){
prefix[i]=prefix[i-1]+a[i];
maxnum=max(maxnum,prefix[i]); 
}
int l,r;
for(l=0;l<n;l++){
for(r=l+1;r<n;r++){
maxnum=max(maxnum,prefix[r]-prefix[l]);
} 
}
cout<<maxnum<<endl;
return 0;
} 

时间复杂度优化

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;  // 输入序列的长度
    int a[N];   // 存储序列的数组

    // 输入数组中的元素
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    // 初始化当前子数组和和最大子数组和
    int current_sum = a[0];
    int max_sum = a[0];

    // 从第二个元素开始遍历
    for (int i = 1; i < N; ++i) {
        // 选择是继续加上当前元素，还是从当前元素重新开始子数组
        current_sum = max(a[i], current_sum + a[i]);
        
        // 更新最大子数组和
        max_sum = max(max_sum, current_sum);
    }

    // 输出最大子段和
    cout << max_sum << endl;

    return 0;
}

原文地址：https://blog.csdn.net/m0_73096516/article/details/143808414

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！