opt.rb

# range of random N_i
$range = 20

# parameter L
$l = 10

$debug = false

# go!
$i_max = 4 * $l

# create random N_i vector
def gen_n
  n = [ ]
  $i_max.times do |i|
    ni = 1 + rand($range)
    n.push(ni)
  end
  return n
end

# unoptimized term (using abs and max)
def t(n, c, i)
  if (i < c) 
    ic = '<'
  elsif i == c
    ic = '='
  else
    ic = '>'
  end
  d = (i - c).abs
  m = [d, $i_max - d].min
  if $debug
    dir = d < ($i_max - d) ? 'L' : 'R'
    puts "c = #{c}, i = #{i}, dir = #{dir}, ic = #{ic}" 
  end
  n[i - 1] * m
end

def sum(n, c)
  zl = 2 * $l
  if $debug
    if c <= zl
      i_split = zl + c - 1
      order = 'LR'
    else
      i_split = c - zl
      order = 'RL'
    end
    puts "c = #{c}, i_split = #{i_split}, order = #{order}"
  end
  s = 0
  $i_max.times do |im|
    i = im + 1
    if $debug
      if i == i_split + 1
        puts " (split)"
      end
    end
    s += t(n, c, i)
  end
  return s
end

# optimized stuff

def tLR(n, c)
  zl = 2 * $l
  vl = 4 * $l
  s = 0
  i = 1
  i1 = c - 1
  while i <= i1
    s += n[i - 1] * (c - i)
    i += 1
  end
  i = c + 1
  i2 = zl + c - 1
  while i <= i2
    s += n[i - 1] * (i - c)
    i += 1
  end
  i = zl + c
  i3 = vl
  while i <= i3
    s += n[i - 1] * (vl - (i - c))
    i += 1
  end
  return s
end

def tRL(n, c)
  zl = 2 * $l
  vl = 4 * $l
  s = 0
  i = 1
  i1 = c - zl
  while i <= i1
    s += n[i - 1] * (vl - (c - i))
    i += 1
  end
  i = c - zl + 1
  i2 = c - 1
  while i <= i2
    s += n[i - 1] * (c - i)
    i += 1
  end
  i = c + 1
  i3 = vl
  while i <= i3
    s += n[i - 1] * (i - c)
    i += 1
  end
  return s
end

def sum_optimized(n, c)
  zl = 2 * $l
  if c <= zl
    s = tLR(n, c)
  else
    s = tRL(n, c)
  end
  return s
end

# fast dt prediction

def dtLR(n, c)
  if c == 0
    return 0
  end
  zl = 2 * $l
  vl = 4 * $l
  s = 0
  i = 1
  i1 = c
  while i <= i1
    s += n[i - 1]
    i += 1
  end
  i = c + 1
  i2 = zl + c
  while i <= i2
    s -= n[i - 1]
    i += 1
  end
  i = zl + c + 1
  i3 = vl
  while i <= i3
    s += n[i - 1]
    i += 1
  end
  return s
end

def dtRL(n, c)
  zl = 2 * $l
  vl = 4 * $l
  return -dtLR(n, c - zl)
end

def delta_t(n, c)
  zl = 2 * $l
  vl = 4 * $l
  if c < 0 || c > vl
    return nil
  end
  if c <= zl
    dt = dtLR(n, c)
  else
    dt = dtRL(n, c)
  end
  return dt
end

# faster dt prediction
def delta_t2(n, c)
  zl = 2 * $l
  vl = 4 * $l
  if c < 0 || c > vl
    return nil
  end
  if c == 0
    return 0
  end
  if c == 1
    return delta_t(n, 1)
  end
  dt = 0
  if c <= zl
    dt = delta_t2(n, c - 1) + 2 * (n[c - 1] - n[zl + c - 1])
    return dt
  else
    dt = -delta_t2(n, c - zl)
    return dt
  end
end

def max_sum(n)
  zl = 2 * $l
  puts "change dir after c = #{zl}"
  c_max = 0
  t_max = 0
  t_last = 0
  q = 0
  dt = 0
  dt_opt = 0
  dt_opt2 = 0
  $i_max.times do |cm|
    c = cm + 1
    t = sum(n, c)
    t_opt = sum_optimized(n, c)
    if c == 1
      dt = 0
    else
      dt = t - t_last
    end
    dt_opt = delta_t(n, c - 1)
    dt_opt2 = delta_t2(n, c - 1)
    q += dt
    puts "=> c = #{c}, t = #{t}, dt = #{dt}, dt_opt = #{dt_opt}, dt_opt2 = #{dt_opt2}, q = #{q}"
    if t != t_opt
      puts "error: t = #{t}, but t_opt = #{t_opt}!"
    end
    if dt != dt_opt
      puts "error: dt = #{dt}, but dt_opt = #{dt_opt}!"
    end
    if dt_opt != dt_opt2
      puts "error: dt_opt = #{dt_opt}, but dt_opt2 = #{dt_opt2}!"
    end
    if t > t_max
      c_max = c
      t_max = t
    end
    t_last = t
    if c == zl
      puts " (change dir)"
    end
  end
  return c_max, t_max
end

puts "l = #{$l}"

n = gen_n
puts "n = #{n}"

c_max, t_max = max_sum(n)
puts "n = #{n}"
puts "c_max = #{c_max}, t_max=#{t_max}"

http://math.stackexchange.com/questions/829139/optimization-problem-maximize-the-sum-of-minimum