CODEWITHSUNDEEP
pythonalgorithmsorting
OLIVER.KOO
OLIVER.KOO

Reputation: 5993

Dividing array so sum of subarray maximums is minimised

I can only think of a brute force way to solve this. Interested to see what Algo SO community would come up with.

Giving an arr a and an integer x (1<x<=len(a)). Wihout reordering the array divide the array into x subarrays s1, s2....sx such that the sum of max(s1) + max(s2)....+ max(sx) is the minimum out of all possible combinations of sum of subarrays (see example below). return an array with x-1 indexes containing the index i (not inclusive) where the split happens a[0:i], a[i+1:i2], a[i2+1: i3].....a[ix:].

Example:

a = [10,30,40,20,50]
x = 2
return = [1]

splitting the array at index 1 into [10] and [30,40,20,50]

would result max([10]) + max([30,40,20,50]) = 60 which is the minimum out of all other ways to split array.

other possible splits -

Upvotes: 1

Views: 1183

Answers (4)

mohit tyagi
mohit tyagi

Reputation: 19

Recursion with back tracking can be used(which can then be converted to DP for optimization)

class Solution {
  static int ans=Integer.MAX_VALUE;
  public static void main(String[] args) {
        ans=Integer.MAX_VALUE;
        int[] nums = {10, 5, 9,3,8};
        int K = 3;
        // 2D array to store the max value of all possible subarrays
        //maxValue[i][j]=maximum value in subarray i...j
        int[][] maxValue = new int[nums.length][nums.length];
        for(int i=0;i<nums.length;i++){
          int max=nums[i];
          for(int j=i;j>=0;j--){
            if(nums[j]>max){
              max=nums[j];
            }
            maxValue[j][i]=max;
          }
        }
        findMinSum(maxValue,0,nums.length-1,K-1,0);
        System.out.println(ans);

  }

  public static void findMinSum(int[][] maxValue,int startIndex,int endIndex,int k,int sumSoFar){
    System.out.println("startIndex="+startIndex+" sumSoFar="+sumSoFar);
    if(k==0){ // no more subarrays to be divided so use the max in this array itself
      sumSoFar+=maxValue[startIndex][endIndex];
      if(sumSoFar<ans){
        ans=sumSoFar;
      }
    } else {
      for(int index=startIndex;index<=endIndex-k;index++){
       // consider all possible starting point and leave space for 
      // upcoming array partitions(endIndex-k)
          findMinSum(maxValue,index+1,endIndex,k-1,sumSoFar+maxValue[startIndex][index]);
      }
    }

  }
}

Upvotes: -1

Alain T.
Alain T.

Reputation: 42143

Brute force isn't that bad if you can structure it to use memoization.

The approach it to recursively make a left-right split to determine the best solution combining each left-side prefix with the best solution for one less split of the right-side. Since this is going to compute the same right side splits multiple times, memoization (keeping past results in memory for reuse) will short circuit most of the exploration branches.

from functools import lru_cache
from itertools import accumulate
def minMaxSum(A,x):
    
    @lru_cache()                # memoization for
    def findBest(start,splits): # best split from start position to end of A

        R = A[start:] # right-side/remaining elements

        # base cases (no recursion)
        if splits == 1:      return max(R),[R]
        if splits == len(R): return sum(R),[[r] for r in R]
        
        # progressively increasing size of left side subarray
        bestSum   = sum(R)+1           
        maxLeft   = 0
        for i,r in enumerate(R[:len(R)-splits+1],1):
            if r >= bestSum: break   # won't improve on best at this point
            maxLeft = max(maxLeft,r) # max for left side          
            subSum,subArrays = findBest(start+i,splits-1) # recurse right side
            subSum += maxLeft
            if subSum>=bestSum: continue # track improvement to best solution
            bestSum   = subSum
            bestSplit = [R[:i],*subArrays] # left side + best right side solution
        return bestSum,bestSplit
    
    # convert to break indexes and return solution
    maxSum,subArrays = findBest(0,x)
    breaks = list(accumulate(map(len,subArrays)))[:-1]
    return breaks,maxSum,subArrays

output:

print(*minMaxSum([10,30,40,20,50],2))
# [1] 60 [[10], [30, 40, 20, 50]]
    
print(*minMaxSum([10,30,40,20,50],3))
# [1, 2] 90 [[10], [30], [40, 20, 50]] 

print(*minMaxSum([40,30,40,20,50],3))
# [3, 4] 110 [[40, 30, 40], [20], [50]]

print(*minMaxSum([40,25,30,45,40,20,35,50],5))
# [1, 2, 5, 6] 180 [[40], [25], [30, 45, 40], [20], [35, 50]]

A = [i%5+1 for i in range(37)]
x = 11
print(*minMaxSum(A,x))
# [1, 2, 5, 6, 7, 10, 11, 12, 35, 36] 27
# [[1], [2], [3, 4, 5], [1], [2], [3, 4, 5], [1], [2],
# [3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [1], [2]]

Upvotes: 0

btilly
btilly

Reputation: 46408

This is a dynamic programming problem.

First build up the following data structure.

for each position in the array
    for each count of how many splits
        (current max, sum of maxes, position of last split)

For example in your problem the data structure would look like this:

[   # One group, no splits
    [(10, 10, 0)], # 2 groups, 1 split
    [(30, 30, 0), (30, 40, 1)],
    [(40, 40, 0), (40, 50, 1), (40, 80, 2)],
    [(40, 40, 0), (20, 50, 1), (20, 70, 3)],
    [(50, 50, 0), (50, 60, 1), (50, 100, 2)], # the choices are equal
]

This can be created with a straightforward double loop. You start off with [[(a[0], a[0], 0)]]. And to figure out the i, j entry you have to look at starting a new group after the (i-1, j-1) entry or adding the current element to the last group in the (i-1, j) entry.

Once you have this, start with the last position of the array and the desired number of splits. The data structure tells you where the last split was, and you go to that position and down one split to find where the one before was. Follow that cookie crumb trail back and you'll find all of the splits.

In your example, the (len(a), x) entry is at (4, 1) and has value (50, 60, 1). The previous entry is at (1, 0) and has value (10, 10, 0). We ignore the split at the boundary and get [1] as the answer.

If you wanted to make x=3, then you'd start at (50, 100, 2), go back to (40, 50, 1), then to (10, 10, 0) and get an answer of [1, 2].

Upvotes: 3

karl
karl

Reputation: 101

For Max(sx) to become as small as possible, we should always strive to create subarrays with as small numbers as possible. So simply divide the input list into single-element lists with the smallest possible value:

arr = [10,30,40,20,50]
n = 2
a = []

def subarray(a):
    r = []
    while (len(r) <= n-2):
        r.append(a[:1])
        a = a[1:]
    r.append(a)
    return r

def calculate(a):
    r = 0
    for i in subarray(a):
        r += i[-1]
    return r

print(calculate(arr))

Upvotes: 0

Related Questions