#include<bits/stdc++.h> using namespace std; int maxSubArray(int* nums, int numsSize){ int ms=INT_MIN,dp=0; for(int i=0;i<numsSize;i++) { dp=fmax(nums[i],dp+nums[i]); if(dp>=ms) ms=dp; } return ms; } int main() { int nums[100]; int n; cin>>n; for(int i=0; i<n; i++) cin>>nums[i]; cout<<maxSubArray(nums,n); return 0; }

这是一段C++代码，用于求解最大子数组和问题。使用的是动态规划的思想，具体实现如下：

- 定义一个变量ms表示当前最大的子数组和，初始值为INT_MIN。
- 定义一个变量dp表示当前位置的最大子数组和，初始值为0。
- 遍历数组，对于每个位置i，更新dp的值为fmax(nums[i],dp+nums[i])，即取当前元素和之前的最大子数组和加上当前元素的较大值。
- 如果dp的值大于等于ms，更新ms的值为dp。
- 最终返回ms的值，即为最大子数组和。

该算法的时间复杂度为O(n)，其中n为数组长度。

相关问题

#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[n],b[n]; for(int i=0;i<n;i++) cin>>a[i]>>b[i]; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(a[i]==a[j]) { b[i]+=b[j]; } } } int max=0; for(int i=0;i<n;i++) { if(max<b[i]) max=b[i]; } for(int i=0;i<n;i++) { if(max==b[i]) { cout<<a[i]<<" "<<b[i]<<endl; break; } } return 0; }时间优化

这段代码可以通过排序来进行优化，具体做法是，将输入的 a 和 b 值组成的二元组按照 a 值从小到大排序，然后顺序遍历这个排序后的数组，统计每个 a 值对应的 b 值的和，直到遇到一个 a 值与前面不同的元素，就可以输出之前统计的 a 值和 b 值的和了。

代码示例：

#include<bits/stdc++.h>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i].first >> nums[i].second;
    }
    sort(nums.begin(), nums.end(), cmp); // 按照 a 值排序
    int sum = nums[0].second, max_sum = sum, max_a = nums[0].first;
    for (int i = 1; i < n; i++) {
        if (nums[i].first == nums[i - 1].first) { // 如果 a 值相同，累加 b 值
            sum += nums[i].second;
        } else { // 否则更新最大值，并记录新的 a 值和 b 值的和
            if (sum > max_sum) {
                max_sum = sum;
                max_a = nums[i - 1].first;
            }
            sum = nums[i].second;
        }
    }
    if (sum > max_sum) { // 处理最后一组数据
        max_sum = sum;
        max_a = nums[n - 1].first;
    }
    cout << max_a << " " << max_sum << endl;
    return 0;
}

时间复杂度为 O(n log n)，空间复杂度为 O(n)。

题目描述 已知一个从小到大排列的n个数的序列，现在要求在这个序列中删除一个数x，使得序列仍然升序，然后将剩余数据输出；如果x不在原始序列中，则把原始序列输出。（x的大小没有特殊说明） 输入 共3行； 第一行，一个整数n（1≤n≤100）； 第二行，n个长整型范围内的整数，用空格隔开； 第三行，一个长整型范围内的整数x。 输出 剩余数据从小到大输出，相邻两数用一个空格隔开。 样例 输入 5 1 3 5 7 9 5 输出 1 3 7 9 请用c++语言编码 头文件用#include <bits/stdc++.h> using namespace std;

#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin >> n;

vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}

int x;
cin >> x;

bool found = false;
for (int i = 0; i < n; i++) {
if (nums[i] == x) {
found = true;
nums.erase(nums.begin() + i);
break;
}
}

if (found) {
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
} else {
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
}

return 0;
}