优化算法的技巧

Question

我会尽量表达这个问题，而不会让它听起来像我在寻找家庭作业的答案(这只是算法的练习问题)。

您有一个数字数组，其中每个值最多可以出现在2x1，3，5，5，1，2，3中，检查从一个值到另一个实例的和(5 +2+ 5) (2 +5+1+ 2)

找出这样的总和的最大值的算法。

我想出了一个非常简单的算法：

iterate through the array (for i=1 to n)
iterate through the remaining array (for j=i+1)
if A[i] == A[j]
    s = 0
    iterate through the values between those two points (for k=i to j)
        s = s + A[k]
    maxVal = max(maxVal,s)

我可以采取哪些步骤来优化算法。(或任何有关该问题的演算法)。显然，这个解决方案是第一个出现在我脑海中的解决方案，但我很难设想出更有效的更好的解决方案。

编辑:为了这个问题，我只想说所有的元素都是正向的

Answer 1

计算累积和数组：

C[0] = A[0]  
for i = 1 to n  
  C[i] = C[i - 1] + A[i]  
A[1 3 5 2 5 1 2 3]  
C[0 1 4 9 11 16 17 19 22]  

当发现对时使用这些值：

  Sum(i to j) = C[j] - C[i - 1]

P.S.所有元素都是正的吗？