小编kha*_*las的帖子

我最近接受了采访,在那里我被问到以下算法问题.我无法找到O(n)解决方案,也无法找到谷歌的问题.

给定整数的数组A [a_0 ... a_(n-1)](+ ve和-ve).形成一个数组M [m_0 ... m_(n-1)],其中m_0 = 2,m_i在[2,...,m_(i-1)+1]中,使得产品总和最大,即我们必须最大化a_0*m_0 + a_1*m_1 + ... + a_(n-1)*m_(n-1)

例子

input  {1,2,3,-50,4}
output {2,3,4,2,3}

input  {1,-1,8,12}
output {2,3,4,5}

我的O(n ^ 2)解决方案是从m_0 = 2开始并且只要a_i是+ ve就继续递增1.如果a_i <0,我们必须考虑从2到m_i-1 + 1的所有m_i,并查看哪一个产生产品的最大总和.

请建议线性时间算法.

当针对在AWS等云上部署的大型系统使用SOA时，可以使用两种方法进行服务交互。

1. 将每个服务群集放在内部Elb后面。客户端与相应的elb建立连接池，而elb进行循环平衡。

2. 使用netflix eureka之类的服务发现方法。

当前，我们正在使用第一种方法，其中每个服务群集都位于内部elb后面，并且客户端通过elb进行通信，因此每个客户端实例仅需维护1个池，即与elb端点。

对于第二种方法，我有以下疑问。

1. 迁移到服务发现和智能客户端体系结构（服务客户端知道所有服务实例（通过eureka服务或同等服务）并且内部负载平衡）是否有好处？
2. 在以上情况下，连接池如何工作？当前，每个客户端实例必须维护1个连接池，即与相应服务的Elb连接的池。但是对于富客户端，每个客户端将具有所有服务实例终结点以直接与之通信。在每个请求上建立连接将不是高效的，我想每个客户端拥有如此多的连接池（每个服务实例1个）是过大的。

在以上两个问题上需要输入/建议。