最後活躍 1729533557

修訂 4e670d86fcdd02ce8e3bf1dafcd49d231d3fb647

p1_kadane_algo.cpp 原始檔案
1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long
4#define mod 1000000007
5#define INF 1e18
6#define nl "\n"
7#define pb push_back
8#define eb emplace_back
9/*Note: emplace_back is faster than push_back*/
10#define ppb pop_back
11#define mp make_pair
12#define ff first
13#define ss second
14#define PI 3.141592653589793238462
15#define set_bits __builtin_popcountll
16#define sz(x) ((int)(x).size())
17#define all(x) (x).begin(), (x).end()
18
19long long maxSubarraySum(vector<int> &nums)
20{
21 int n = nums.size();
22 long long mx = LONG_MIN; // maximum sum
23 long long sum = 0;
24
25 for (int i = 0; i < n; i++)
26 {
27
28 sum += nums[i];
29
30 if (sum > mx)
31 {
32 mx = sum;
33 }
34
35 if (sum < 0)
36 {
37 sum = 0;
38 }
39 }
40
41 return mx;
42}
43void solve()
44{
45}
46int main()
47{
48 // ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
49#ifndef ONLINE_JUDGE
50 // freopen("input.txt", "r", stdin);
51 // freopen("output.txt", "w", stdout);
52#endif
53
54 ll t = 1;
55 cin >> t;
56 while (t--)
57 {
58 int n;
59 cin >> n;
60 vector<int> a(n);
61 for (int i = 0; i < n; i++)
62 cin >> a[i];
63 cout << maxSubarraySum(a) << nl;
64 }
65}