- 题目描述:
-
给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值(如果数组中的元素全部为负数,则最大和为0,即一个也没有选)。
- 输入:
-
输入包含多个测试用例,每个测试用例共有两行,第一行是一个整数n(1=<n<=100000),表示数组的长度,第二行依次输入n个整数(整数绝对值不大于1000)。
- 输出:
-
对于每个测试用例,请输出子数组和的最大值。
- 样例输入:
-
6 1 -2 3 5 -1 2 5 6 -1 5 4 -7
- 样例输出:
-
10 14
#include<stdio.h> #include<math.h> #include<string.h> #include<map> #include<algorithm> #include<queue> #include <iostream> using namespace std; const int MAX = 110000 * 2; int sum[MAX]; struct Q { int id, v; } q[MAX]; int front; int rear; void push(int id, int v) { rear++; q[rear].id = id; q[rear].v = v; while (rear - 1 >= front && q[rear - 1].v > q[rear].v) { rear--; q[rear] = q[rear + 1]; } } int query(int id) { while (front <= rear && q[front].id < id) { front++; //队列头超出范围的删除掉 } if (front > rear) return 0; return q[front].v; } void print_q() { for (int i = 0; i <= rear; i++) cout << q[i].id << ":" << q[i].v << " "; cout << endl; } int main() { int n; int i; freopen("in.txt", "r", stdin); while (scanf("%d", &n) != EOF) { sum[0] = 0; for (i = 1; i <= n; i++) { scanf("%d", &sum[i]); sum[i + n] = sum[i]; } for (i = 1; i <= 2 * n; i++) sum[i] += sum[i - 1]; rear = -1; front = 0; push(0, 0); int ans = 0; for (i = 1; i <= 2 * n; i++) { //print_q(); 打印 //tmp即为 i 到 i-n+1 之间的 最大字段和 int tmp = sum[i] - query(i - n + 1); //查询得间距不超过n的最小前缀 //打印 //cout << i << " " << i - n + 1 << " " << query(i - n + 1) << " "<< sum[i] << endl; if (tmp > ans) ans = tmp; push(i, sum[i]); } printf("%d\n", ans); } return 0; }