CareerCup

Calulcate Array sum[n] where for example sum[8] = input[8] + input[7] + input[6] for k = 3

Calculate Array maxFromLeft[n] where for example maxFromLeft[8] = max (sum[0], sum[1], ..., sum[8])

Calculate Array maxFromRight[n] where for example maxFromLeft[8] = max(sum[8], sum[9], ..., sum[n])

Now iterate over sum[n] and at each iteration consider intermediateSum[i] = maxFromLeft[i] + sum[i] + maxFromRight[i]

Answer: Max( intermediateSum[i] ) where i -> 0 to n - 1

Complexity: O(n)

Here is a working dynamic programming iterative solution in C++11.
The solution is O(ranges*data_size) because it does not fully recalculate all following maximums in the row in a loop, but instead just compares value starting at that element with maximum of the previous element. Otherwise the solution would be O(ranges*data_size*data_size). Size complexity is also O(ranges*data_size).
I have not implemented any protection against invalid inputs.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>

std::pair<int, std::vector<std::pair<int, int>>> max_ranges(const std::vector<int>& data, int ranges, int range_size) {
  std::vector<std::vector<int>> cache(ranges + 1, std::vector<int>(data.size()));
  std::vector<std::vector<int>> came_from(ranges + 1, std::vector<int>(data.size(), -1));
  std::vector<std::vector<int>> starting_from(ranges + 1, std::vector<int>(data.size(), -1));

  int last_valid = data.size() - range_size;
  std::vector<int>  range_at(last_valid + 1);
    range_at[0] = std::accumulate(data.begin(), data.begin() + range_size, 0);
  for(int i = 1; i < range_at.size(); ++i)
    range_at[i] = range_at[i - 1] - data[i - 1] + data[i + range_size - 1];

  cache[1][last_valid] = range_at[last_valid];
  starting_from[1][last_valid] = last_valid;
  for(int i = last_valid - 1; i >= 0; --i) {
    if(range_at[i] >= cache[1][i+1]) {
      cache[1][i] = range_at[i];
      starting_from[1][i] = i;
    } else {
      cache[1][i] = cache[1][i+1];
      starting_from[1][i] = starting_from[1][i+1];
    }
  }

  for(int range = 2; range <= ranges; ++range) {
    last_valid -= range_size;
    cache[range][last_valid] = cache[range-1][last_valid + range_size] + range_at[last_valid];
    came_from[range][last_valid] = last_valid + range_size;
    starting_from[range][last_valid] = last_valid;
  }

  last_valid = data.size() - range_size;
  for(int range = 2; range <= ranges; ++range) {
    last_valid -= range_size;
    for(int start = last_valid - 1; start >= 0; --start) {
      int new_val = range_at[start] + cache[range-1][start + range_size];
      if(new_val >= cache[range][start+1]) {
        cache[range][start] = new_val;
        came_from[range][start] = starting_from[range-1][start + range_size];
        starting_from[range][start] = start;
      } else {
        cache[range][start] = cache[range][start+1];
        came_from[range][start] = came_from[range][start+1];
        starting_from[range][start] = starting_from[range][start+1];
      }	
    }
  }

  std::vector<std::pair<int, int>> ranges_res;
  for(int range = ranges, cf = 0; range >= 1; --range) {
    ranges_res.emplace_back(starting_from[range][cf], starting_from[range][cf] + range_size - 1);
    cf = came_from[range][cf];
  }

  return {cache[ranges][0], std::move(ranges_res)};
}

int main() {
  std::vector<int> data = {1, 2, 1, 2, 6, 7, 5, 1};

  auto res = max_ranges(data, 3, 2);
  std::cout << "Max sum: " << res.first << std::endl;
  for(const auto& pr : res.second)
    std::cout << pr.first << ", " << pr.second << std::endl;

  return 0;
}

why can't we find window os size k with largest sum 3 times omitting those numbers from the list each time

why can't we find window of maximum sum with k numbers 3 times and omitting those numbers from the list in each iteration. It would have the complexity of O(3n)

Find 3 biggest intervals, recurse on non intersecting, find max sum.

public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new FileReader("test.txt"));
        int n = in.nextInt();
        int k = in.nextInt();
        int arraySize = in.nextInt();
        int[] a = new int[arraySize];
        for (int i = 0; i < arraySize; i++) {
            a[i] = in.nextInt();
        }

        List<Interval> intervals = getBiggestIntSum(a, n, k, new ArrayList<>());
    }

    static List<Interval> getBiggestIntSum(int[] a, int n, int k, List<Interval> exclude) {
        Queue<Interval> candidates = new PriorityQueue<>(n);
        int left= 0;
        int right = 0;
        int sum = 0;
        while(right < a.length) {
            if(right-left <k) {
                sum += a[right];
                right++;
            } else {
                boolean intersects = false;
                Interval candidate = new Interval(left, right - 1, sum);
                for(Interval exc : exclude) {
                    if (exc.intersects(candidate)) {
                        intersects = true;
                        break;
                    }
                }
                if(!intersects) {
                    if(candidates.size() < n) {
                        candidates.add(candidate);
                    } else {
                        if(candidates.peek().sum < candidate.sum) {
                            candidates.poll();
                            candidates.add(candidate);
                        }
                    }
                }
                sum -= a[left];
                left++;
            }
        }


        List<Interval> candidatesList = candidates.stream().collect(Collectors.toList());
        if(candidatesList.size() == 1)
            return candidatesList;

        List<Interval> intersecting = new ArrayList<>();
        List<Interval> nonIntersecting = new ArrayList<>();
        for (int i = 0; i < candidatesList.size(); i++) {
            Interval candidate = candidatesList.get(i);
            boolean intersects = false;
            for (int j = i+1; j < candidatesList.size(); j++) {
                if(candidate.intersects(candidatesList.get(j))) {
                    intersects = true;
                    break;
                }
            }
            if(!intersects) {
                nonIntersecting.add(candidate);
            } else {
                intersecting.add(candidate);
            }
        }

        int globalSum = 0;
        List<Interval> results = new ArrayList<>();

        if(nonIntersecting.size() == n)
            return  nonIntersecting;
        else if(nonIntersecting.size() > 0) {
            List<Interval> newExclude = new ArrayList<>();
            newExclude.addAll(exclude);
            newExclude.addAll(nonIntersecting);
            List<Interval> tmpResults = getBiggestIntSum(a, n - nonIntersecting.size(), k, newExclude);
            int tmpSum = tmpResults.stream().mapToInt(o -> o.sum).sum() + nonIntersecting.stream().mapToInt(o-> o.sum).sum();
            if(tmpSum > globalSum) {
                globalSum = tmpSum;
                results = tmpResults;
                results.addAll(nonIntersecting);
            }
        }

        for (int i = 0; i < intersecting.size(); i++) {
            Interval candidate = intersecting.get(i);
            List<Interval> newExclude = new ArrayList<>();
            newExclude.addAll(exclude);
            newExclude.add(candidate);
            List<Interval> tmpResults = getBiggestIntSum(a, n -1, k, newExclude);
            int tmpSum = tmpResults.stream().mapToInt(o -> o.sum).sum() + candidate.sum;
            if(tmpSum > globalSum) {
                globalSum = tmpSum;
                results = tmpResults;
                results.add(candidate);
            }
        }

        return results;
    }

    static class Interval implements Comparable<Interval> {
        int left;
        int right;
        int sum;

        public Interval(int left, int right, int sum) {
            this.left = left;
            this.right = right;
            this.sum = sum;
        }

        public boolean intersects(Interval interval) {
            if(left <= interval.left) {
                if(right >= interval.left)
                    return true;
            } else {
                if(left <= interval.right)
                    return true;
            }
            return false;
        }

        @Override
        public int compareTo(Interval o) {
            return Integer.compare(sum, o.sum);
        }
    }

Thanks! Good solution sameer. Just a minor correction

intermediateSum[i] = maxFromLeft[i-k] + sum[i] + maxFromRight[i+k]
When considering the max from right and left, we should eliminate the elements that are already a part of the sum[i], such that there is no overlap.

object MaxWindowSum {

  def getMax(numbers: Seq[Int], k: Int): Seq[Seq[Int]] = {
    val sums = (0 to (numbers.size - k)).map(i => (i, (i to (i+k-1)).map(numbers(_)).sum)).toList
    val sortedSums = sums.sortBy(_._2).reverse

    val solution = getMaxInternal(sortedSums, k, 3)
    getSolutionWindows(solution, numbers, k)
  }

  private def checkSolution(solution: Seq[(Int, Int)], n: Int): Seq[(Int, Int)] = if (solution.size == n) solution else Seq()

  private def getMaxInternal(idxAndNumber: Seq[(Int,Int)], k: Int, n: Int): Seq[(Int, Int)] = {
    val theBest = idxAndNumber.lift(0)
    if (theBest.isDefined && idxAndNumber.size >= n) {
      if(n == 1) {
        //if you are looking for one value only then just take the best
        Seq(theBest.get)
      } else {
        val (rest, overlapped) = idxAndNumber.drop(1).partition(el => {
          val dist = math.abs(theBest.get._1 - el._1)
          dist >= k
        })
        val firstSolution = getMaxInternal(rest, k, n - 1) ++ theBest
        val firstSolutionValue = calcValue(firstSolution)

        if (!overlapped.isEmpty || firstSolution.size < n) {
          //check solution for intersected windows
          val alternativeSolution = getMaxInternal(idxAndNumber.drop(1), k, n)
          val alternativeSolutionValue = calcValue(alternativeSolution)

          if (firstSolutionValue >= alternativeSolutionValue)
            checkSolution(firstSolution, n)
          else {
            checkSolution(alternativeSolution, n)
          }
        } else
          checkSolution(firstSolution, n)
      }
    } else {
      //just nothing more to select - no solution
      Seq()
    }
  }

  private def calcValue(solution: Seq[(Int,Int)]): Long = solution.map(_._2).sum

  private def getSolutionWindows(solution: Seq[(Int, Int)], numbers: Seq[Int], k: Int): Seq[Seq[Int]] =
    solution.sortBy(_._1).map(el => numbers.slice(el._1, el._1 + k))

  def main(args: Array[String]) {
    val solution = getMax(Seq(2,2,4,4,2,2,1,1,1,1,1,1,1,1,1,2,1,2,1,1,1), 3)
//    val solution = getMax(Seq(1,2,1,2,6,7,5,1), 2)
    println("solution: %s, value: %d".format(solution, solution.map(_.sum).sum))
  }

}

Recursively searching for max total of sums in the remaining sub-array for each sum in the present array.

static void Main(string[] args)
{
    int[] arr = new int[] { 1, 2, 1, 2, 6, 7, 5 };
    int w = 2; // window size
    int c = 3; // window count


    int[] startPositions;
    var sum = Sum(arr, w, c, out startPositions, 0);
    Console.WriteLine($"Positions: ({string.Join(", ", startPositions)}), sum = {sum}");
    for (var i = 0; i < startPositions.Length; i++)
    {
        var elements = new int[w];
        for (var j = 0; j < w; j++)
            elements[j] = arr[startPositions[i] + j];

        Console.WriteLine($"Sum #{i + 1}: ({string.Join(", ", elements)})");
    }
    Console.ReadLine();
}

public static int Sum(int[] arr, int wsize, int wcount, out int[] startPositions, int currentwcount)
{
    //Console.WriteLine($"Searching for max {wcount - currentwcount} sums in sub-array: {string.Join(", ", arr)}");
    var maxSum = 0;
    startPositions = new int[0];
    currentwcount++;
    if (arr.Length < wsize)
        return 0;
    var maxIndex = new int[] {  };
    for (var i = 0; i + wsize <= arr.Length; i++)
    {
        var startPos = new int[] { i };
        var currentSum = 0;
        for (var j = i; j <  i + wsize; j++)
            currentSum += arr[j];
        if (currentwcount == wcount)
        {
            if (currentSum > maxSum)
            {
                maxSum = currentSum;
                maxIndex = startPos;
            }
        }
        else if (currentwcount < wcount) // when to exit from recursion
        {
            //Console.WriteLine($"Looking for sum #{currentwcount} in ({string.Join(", ", arr)}) i={i}, max={currentSum}");
            // take sub-array between the current window end and the end of the array and find max-sum combinations in it 
            var subArray = new int[arr.Length - i - wsize];
            for (int j = i + wsize, jj = 0; j < arr.Length; j++, jj++)
                subArray[jj] = arr[j];
            int[] subMsxStartPositions;
            var maxSubSum = Sum(subArray, wsize, wcount, out subMsxStartPositions, currentwcount);
            var currentSumWithSubSum = currentSum + maxSubSum;
            if (currentSumWithSubSum > maxSum)
            {
                //Console.WriteLine($"Found new max total of this array ({string.Join(", ", arr)})={currentSum} and sub-array ({string.Join(", ", subArray)})={maxSubSum}, new MAX = {currentSumWithSubSum}");
                maxSum = currentSumWithSubSum;
                maxIndex = new int[subMsxStartPositions.Length + 1];
                maxIndex[0] = i;
                for (var ii = 0; ii < subMsxStartPositions.Length; ii++)
                    maxIndex[ii + 1] = subMsxStartPositions[ii] + i + wsize;
            }
        }
    }
    startPositions = maxIndex;
    return maxSum;
}

Output:

Positions: (0, 3, 5), sum = 23
Sum #1: (1, 2)
Sum #2: (2, 6)
Sum #3: (7, 5)

def three_subs(arr):
    max_so_far = 0
    max_till_now = 0
    m = [0]
    curr_index = 0
    new_introduced = True
    for item in arr:
        max_till_now += item
        if max_till_now < 0:
            max_till_now = 0
            if not new_introduced:
                curr_index += 1
                m.append(0)
                new_introduced = True
        else:
            m[curr_index] = max(m[curr_index], max_till_now)
            new_introduced = False
    return m


arr = [-1, -2, 3, 4, 5, -700, 1, 2, 8, -100, 4, 5, -200, 99]
print three_subs(arr)

I think it is just a small modification to Kadane's algorithm

def three_subs(arr):
    max_so_far = 0
    max_till_now = 0
    m = [0]
    curr_index = 0
    new_introduced = True
    for item in arr:
        max_till_now += item
        if max_till_now < 0:
            max_till_now = 0
            if not new_introduced:
                curr_index += 1
                m.append(0)
                new_introduced = True
        else:
            m[curr_index] = max(m[curr_index], max_till_now)
            new_introduced = False
    return m


arr = [-1, -2, 3, 4, 5, -700, 1, 2, 8, -100, 4, 5, -200, 99]
print three_subs(arr)

It is a small modification to Kadane's algo, I feel.