美团笔试.回转寿司_美团笔试 回转寿司

题目：在循环数组上求和最大的子数组。
方法一：
不是循环时：正常求。
是循环时：求出和最小的子数组，sum-该值，就是循环时的子数组最大值

#include <bits/stdc++.h>
using namespace std;
#define len 100005 // 有’#‘ 无 ’=‘
int main() {

	int t, n;
	cin >> t; 
	int nums[len], dp[len], dp2[len]; 
	while (t--) {
		int sum = 0;
		cin >> n; //写到while里面 
		for (int i = 0; i < n; ++i) {
			cin >> nums[i];
		}
		for (int i = 0; i < n; ++i) {
			sum += nums[i];
		}
		int _min = INT_MAX, _max = INT_MIN;
		for (int i = 0; i < n; ++i) {
			if (i == 0) {
				dp[i] = dp2[i] = nums[i];
			}
			else {
				dp[i] = max(dp[i - 1] + nums[i], nums[i]);
				dp2[i] = min(dp2[i - 1] + nums[i], nums[i]);
			}
			_min = min(_min, dp2[i]);
			_max = max(_max, dp[i]);
		}
		cout << max(_max, sum - _min) << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法二：
不是循环时：正常求。
是循环时：nums[i]的最大值为：sums[i] + i + 1后缀和的最大值

#include <bits/stdc++.h>
using namespace std;
#define len 100005
int main() {
	//前缀和pre 后缀和post  最大后缀和_max
	//dp[i] = max(dp[i - 1] + nums[i], nums[i], pre[i] + _max[i+1]) ;
	int t, n;
	cin >> t; 
	int nums[len], pre[len], post[len], _max[len], dp[len]; 
	while (t--) {
		cin >> n;
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			cin >> nums[i];
		}
		for (int i = 0; i < n; ++i) {
			if (i == 0) pre[i] = nums[i];
			else pre[i] = pre[i - 1] + nums[i];
		}
		for (int i = n - 1; i >= 0; --i) {
			if (i == n - 1) {
				post[i] = nums[i];
				_max[i] = post[i];
			}
			else {
				post[i] = post[i + 1] + nums[i];	
				_max[i] = max(_max[i + 1], post[i]);
			}
		}	
		int ans = INT_MIN;
		for (int i = 0; i < n; ++i) {
			if (!i) dp[i] = nums[i];
			else dp[i] = max(dp[i - 1] + nums[i], nums[i]);
			ans = max(ans, dp[i]);
		}
		for (int i = 0; i < n; ++i) {
			if (i + 1 < n) dp[i] = max(dp[i], pre[i] + _max[i + 1]);	
			ans = max(ans, dp[i]);
		}
		cout << ans << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43