possible solution for circle array problem.

circlemax.py

# -*- coding: utf-8 -*- 

'''
A circular array A[1, . . . , n] is an array such that n ≥ 3 and A[1] and A[n] are considered to be adjacent elements just like A[1] and A[2], A[2] and A[3], etc., are adjacent.
We are given a circular array A[1, . . . , n] of non-negative integers. For any i, j ∈ {1, 2, . . . , n} such that i != j, dist(i, j) = max {|i − j|, n − |i − j|}.
Design a linear time algorithm that computes a maximum number t such that for some i, j ∈ {1, 2, . . . , n}, i != j, t = A[i] + A[j] + dist(i, j).
'''

def distant(i, j, n):
    dis = abs(j-i)
 
    # this won't work for '<'
    if ((n-dis) > dis):
        dis = n-dis
 
    return dis
 
def evaluate(aa, i, j, n):
    dis = distant(i,j,n)
    val = aa[i] + aa[j] + dis
 
    return (dis, val)
 
def move_iter(aa, iter_cur, iter_other, bound, n):
    iter_new = iter_cur
    (dist_cur, val_cur) = evaluate(aa, iter_cur, iter_other, n)
 
    TimeO = 0 # use to compute time complexity
    for x in xrange(iter_cur, bound):
        TimeO+=1
 
        (dist_new, val_new) = evaluate(aa, x, iter_other, n)
        if (val_new > val_cur):
            iter_new = x
            val_cur = val_new
 
    return (iter_new, TimeO)
 
def solv(a):
    iter_i_max = 0
    iter_j_max = 0
    val_max = 0
    dist_max = 0
 
    n = len(a)
    aa = a+a # concatenate to a long array to avoid index manipulation
    bound = n/2 # half of the circle
 
    # two iterators, run from the start point
    iter_i = 0
    iter_j = 1
 
    TimeO = 0 # use to compute time complexity
    while (True):
        # move one forward to get larger value, stop when it hits the bound
        (iter_j_new, Time_j) = move_iter(aa, iter_j, iter_i, iter_i+bound+1, n)
        # move one forward to get larger value, stop when it meets the other one.
        (iter_i_new, Time_i) = move_iter(aa, iter_i, iter_j_new, iter_j_new, n)
        TimeO = TimeO + Time_i + Time_j
 
        (dist_cur, val_cur) = evaluate(aa, iter_i_new, iter_j_new, n)
        if (val_cur > val_max):
            iter_i_max = iter_i
            iter_j_max = iter_j
            val_max = val_cur
            dist_max = dist_cur
           
        # back to the start point
        if (iter_i_new >= n):
            break
        
        # move forward
        iter_i = iter_j_new
        iter_j = iter_j_new+1
 
    # normalize the index
    if (iter_j_max >= n):
        (iter_i_max, iter_j_max) = (iter_j_max-n, iter_i_max)
 
    return (iter_i_max, aa[iter_i_max], iter_j_max, aa[iter_j_max], dist_max, val_max, TimeO)
 
#==============================
# test
import random
def greed(a):
    m = 0
    mi = 0
    mj = 0
    mdis = 0
    n = len(a)
    for i in xrange(0, n):
        for j in xrange(i+1, n):
            (ndis, nm) = evaluate(a, i, j, n)
            if (nm > m):
                mi = i
                mj = j
                mdis = ndis
                m = nm
    return (mi, a[mi], mj, a[mj], mdis, m)
 
def randarr(arrmax, arrlen):
    a = []
    while (arrlen > 5):
        random.seed()
        a+=random.sample(xrange(1, arrmax+1), 5)
        arrlen-=5
    
    random.seed()
    a+=random.sample(xrange(1, arrmax+1), arrlen)
    return a
 
def test(arrmax, arrlen, times):
    k=0.0
    result = [True]
    for i in xrange(times):
        a = randarr(arrmax, arrlen)
        lv = greed(a)
        rv = solv(a)
        k+=(float(rv[-1])/len(a))
        if (lv[-1] != rv[-2]):
            result = [False, a, lv, rv]
            break
 
    result += [k/times,]
    return result
 
if __name__ == '__main__':
    a = test(100, 200, 10)
    if not a[0]:
        print a[:-1]
    else:
        print "Pass, time=O({0}*N).".format(a[-1])