一道Google算法题：给一个长度为2N的非负整数数组arr。现在每次删除最左端或最右端的元素，重复N次为止。请返回被删掉的数字之和最大是多少。

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了一道Google算法题：给一个长度为2N的非负整数数组arr。现在每次删除最左端或最右端的元素，重复N次为止。请返回被删掉的数字之和最大是多少。，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1453字，纯文字阅读大概需要3分钟。

内容图文

题目链接：https://www.nowcoder.com/discuss/205633?type=2&order=3&pos=184&page=1
题目来源：牛客网

题目描述

2、给一个长度为2N的非负整数数组arr。现在每次删除最左端或最右端的元素，重复N次为止。请返回被删掉的数字之和最大是多少。

例：

• [1,2,3,4] => 4 + 3 = 7
• [1,100,2,8] => 1 + 100 = 101
• [98, 52, 67, 89]=> 98+89 = 187

解题思路：滑动窗口

学过计算机网络的人应该都知道有滑动窗口这个概念。这里设置一个长度为N的滑动窗口，假设有 [a, b, c, d, e, f , g, h,i]。算法步骤如下：

• 1、滑动窗口取左区间，滑动窗口的内容为[a, b, c, d]，max=a+b+c+d
• 2、滑动窗口移动一个位置，此时滑动窗口的内容为[i, a, b, c]， 作如下判断：

tmp = max - d + i;
if tmp > max:
	max = tmp

• 3、重复步骤2，直至滑动窗口为[f, g, h, i], 此时的max是解。

算法实现

#include<stdio.h>

unsigned long long slide_window(int *arr, unsigned int size)
{
	unsigned int half = size / 2;
	unsigned int slide_window[half];
	unsigned int i, j;
	unsigned long long max, tmp;
	max = 0;
	tmp = 0;
	for (i = 0; i < half; i++)
	{
		// here, variable max may overflow in real produce environment.
		max += (unsigned long long)arr[i];
	}
	for (j = 0; j < half; j + +)
	{
		// here, variable tmp may overflow in real produce environment.
		tmp = max - (unsigned long long)arr[i] + (unsigned long long)arr[size-j];
		i--;
		if (tmp > max)
		{
			max = tmp;
		}
	}
	return max;

int main()
{
	unsigned int arr[4, 9, 130, 21, 10, 2, 100, 33, 1, 3];
	unsigned long long resutl = 0;
	result = slide_window(arr, sizeof(arr)/sizeof(char))
	printf("result is: %lld", result);
	return 0;
}

内容总结

以上是互联网集市为您收集整理的一道Google算法题：给一个长度为2N的非负整数数组arr。现在每次删除最左端或最右端的元素，重复N次为止。请返回被删掉的数字之和最大是多少。全部内容，希望文章能够帮你解决一道Google算法题：给一个长度为2N的非负整数数组arr。现在每次删除最左端或最右端的元素，重复N次为止。请返回被删掉的数字之和最大是多少。所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---