每日一题之最大子段和

给定由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;
}