Sub-arrays of maximal sum

Sub-arrays of maximal sum

Another puzzle problem from this blog. "You are given an array of n integers, each of which may be positive, negative or zero. Give an algorithm to identify the start and end index, i and j, of the interval whose elements form the maximal sum of all possible intervals. Assume j >=i. e.g. {1 3 -8 2 -1 10 -2 1} -> i=3, j=5 - sum=11.

Python

'''Find sub-arrays of maximal sum

   e.g. {1 3 -8 2 -1 10 -2 1} -> i=3, j=5 - sum=11

   http://basicalgos.blogspot.com/2012/05/52-find-sub-array-of-max-sum.html
'''

import functools

#Compute all the intervals of the sequence t per the definition
#above. e.g. for [1, 2, 3] compute [[1], [1, 2], [1, 2, 3], [2],
#[2, 3], [3]]. 
#Decorate the intervals with their start and end indices and the
#interval sum.
def intervals (t):
  def f (acc, i):
    def row (i, t):
      s = t[i:]
      def f (acc, j):
         indices=(i, i+j-1)
         interval=s[0:j]
         return acc + [(indices, interval, sum (interval, 0))]
      return functools.reduce (f, list (range (1, len (s) + 1)), [])
    return acc + row (i, t)
  return functools.reduce (f, list (range (0, len (t))), [])
  
#x, the input sequence.
x=[1, 3, -8, 2, -1, 10, -2, 1]

#Print the intervals of x with maximal sum.
res = intervals (x)
def f (m, t): 
  (_,_,n)=t ; return max (m, n)
maxsum = functools.reduce (f, res, 0)
for t in res:
  (indices, interval, total)=t
  if (total == maxsum):
    print (str(t)) #An interval of maximal sum.

C++

#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <functional>

typedef std::pair<std::size_t, std::size_t> indicies_t;
inline std::size_t& fst (indicies_t& i) { return i.first; }
inline std::size_t& snd (indicies_t& i) { return i.second; }
inline std::size_t fst (indicies_t const& i) { return i.first; }
inline std::size_t snd (indicies_t const& i) { return i.second; }
void print_indicies (indicies_t const& p);

typedef std::vector<int> interval_t;
inline std::size_t len (interval_t const& i) { return i.size(); }
interval_t take (int k, interval_t const& lst);
interval_t drop (int k, interval_t const& lst);
inline int sum (interval_t const t)
{ 
  int tot=std::accumulate (t.begin(), t.end(), 0, std::plus<int>());

  return tot;
}
interval_t range (int begin, int end);
void print_interval (interval_t const& s);

struct interval_info_t
{
  indicies_t indicies; //(0, 2)
  interval_t interval; //e.g. [1, 2, 3]
  int total; //6
};
void print_interval_info (interval_info_t const& i);

typedef std::vector<interval_info_t> interval_info_set_t;

struct inner_f
{
  interval_t s;
  std::size_t i;

  inner_f (interval_t const& s, std::size_t i) 
    : s (s), i (i) 
  {}

  interval_info_set_t operator() 
  (interval_info_set_t acc, std::size_t j)
  {
    indicies_t indicies;
    fst (indicies) = i;
    snd (indicies) = i + j - 1;
    interval_t interval = take (j, s);
    int total = sum (interval);

    interval_info_t interval_info;
    interval_info.indicies = indicies;
    interval_info.interval = interval;
    interval_info.total = total;

    acc.push_back (interval_info);
  
    return acc;
 }
};

interval_info_set_t row (std::size_t i, interval_t const& t)
{
  interval_t s = drop (i, t);
  interval_t rg = range (1, len (s) + 1);
  
  return std::accumulate (
    rg.begin(), rg.end(), interval_info_set_t(), inner_f (s, i));
}

struct outer_f
{
  interval_t t;
  outer_f (interval_t const t) : t (t) {}

  interval_info_set_t operator() 
    (interval_info_set_t acc, std::size_t i) const
  {
    interval_info_set_t res=row (i, t);
    std::copy (res.begin(), res.end(), std::back_inserter (acc));
  
    return acc;
  }
};

interval_info_set_t intervals (interval_t const& t)
{
  interval_t rg = range (0, len (t));
  
  return std::accumulate (
    rg.begin(), rg.end(), interval_info_set_t (), outer_f (t));
}

inline int find_max (int m, interval_info_t const& t)
{
  return (std::max)(m, t.total);
}

//--driver

int main ()
{
  int data[] = {1, 3, -8, 2, -1, 10, -2, 1};
  interval_t input(data, data + sizeof(data)/sizeof(int));
  interval_info_set_t ivals = intervals (input);
  int maxsum = std::accumulate (ivals.begin(), ivals.end(), 0, find_max);

  for (std::size_t i = 0; i < ivals.size(); ++i)
    {
      if (ivals[i].total==maxsum)
 print_interval_info (ivals[i]); //An interval of maximal sum.
    }
  
  return 0;
}

//-- tools

interval_t take (int k, interval_t const& lst)
{
  if (k <= 0) return interval_t ();
  if (lst.size() == std::size_t (0)) return interval_t ();

  interval_t t = take (k-1, interval_t (++(lst.begin()), lst.end()));
  interval_t res (t.size()+1);
  res[0] = lst[0];
  for (std::size_t i = 0; i < len (t); ++i)
    res [i+1] = t[i];

  return res;
}

interval_t drop (int k, interval_t const& lst)
{
  if (k <= 0) return lst;
  if (lst.size () == 0) return interval_t ();

  return drop (k - 1, interval_t (++(lst.begin()), lst.end()));
}

interval_t range (int begin, int end)
{
  interval_t buf;
  for(int i = begin; i < end; ++i) buf.push_back (i);

  return buf;
}

void print_indicies (indicies_t const& p)
{
  std::cout << "(" << fst (p) << ", " << snd (p) << ")";
}

void print_interval (interval_t const& s)
{
  std::cout << "["; 
  std::ostream_iterator<int> out_it (std::cout, ", ");
  std::copy (s.begin(), s.end(), out_it);
  std::cout << "],"; 
}

void print_interval_info (interval_info_t const& i)
{
  std::cout << "(";
  print_indicies (i.indicies);
  print_interval (i.interval);
  std::cout << i.total;
  std::cout << ")\n";
}