程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> acdream 1682(有環的最大連續和)

acdream 1682(有環的最大連續和)

編輯:關於C++

題意:有n個數字圍成一個圈,然後從圓圈拿走連續的一些數,問拿走的數的和的最大值是多少。

題解:普通最大連續和的做法,如果前面累加的數加當前數是大於最大值就更新最大值,如果小於0就把累加值清零,這個是有環的,那麼可以從兩種情況考慮,一種是普通的最大連續和找到的最大值,另一種就是頭尾拼接的,把所有數取相反數,然後找到最大連續和,那麼用總和sum加這個數就是頭尾拼接的最大值,取兩種情況較大的就是解。

 

#include 
#include 
using namespace std;
const int N = 200010;
int n, s[N];

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &s[i]);
			sum += s[i];
		}
		int res = 0, maxx = 0;
		for (int i = 1; i <= n; i++) {
			res += s[i];
			if (res > maxx)
				maxx = res;
			if (res < 0)
				res = 0;
		}
		for (int i = 1; i <= n; i++)
			s[i] = -1 * s[i];
		int res2 = 0, maxx2 = 0;
		for (int i = 1; i <= n; i++) {
			res2 += s[i];
			if (res2 > maxx2)
				maxx2 = res2;
			if (res2 < 0)
				res2 = 0;
		}
		printf("%d\n", max(maxx, sum + maxx2));
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved