Задача поиска подмножеств с минимальной суммой Amazon

def idxmax(lst):
    '''Поиск индекса наибольшего числа в списке'''
    index_max = 0
    for index, item in enumerate(lst[1:]):
        if item > lst[index_max]:
            index_max = index + 1
    return index_max
 
 
def Find_first_day_candidates(task_complexity_list, n_days):
    '''Поиск всех задач-кандидадатов стать главной в первый день из списка задач'''
    n = len(task_complexity_list) # число задач в списке
    if (n == 0) or (n_days == 0): # Нет решения, выход из рекурсии
        return [[]]
    elif (n == 1): # одно решение, выход из рекурсии
        return [[task_complexity_list[0]]]
    elif (n >= 1 and n_days == 1): # одно решение, выход из рекурсии
        return [[max(task_complexity_list)]]
    
    last_candidate_index = 0
    candidates_list = []
    for current_candidate_index, task_complexity in enumerate(task_complexity_list):
        if task_complexity >= task_complexity_list[last_candidate_index]:
            # найден очередной кандидат, добавим его в список и назначаем его последним
            last_candidate_index = current_candidate_index
            answer_list = Find_first_day_candidates(task_complexity_list[current_candidate_index + 1:], n_days-1)
            # Свели задачу к задаче меньшего размера
            for prev_candidates in answer_list:
                seq = [task_complexity] + prev_candidates
                candidates_list.append(seq)
    return candidates_list
 
 
def Amazon_calc(task_complexity_list, n_days):
    '''Основная функция решения задачи от Amazon'''
    
    max_complexity_index = idxmax(task_complexity_list) # Индекс самой сложной задачи в условии
    
    # Решение прямой задачи [3, 1, 4, 5, 9], n_days=4 (задача А)
    task_forward = Find_first_day_candidates(task_complexity_list[:max_complexity_index+1], n_days)
    print('\n Ответы задачи А:', task_forward)  
    
    # Решение обратной задачи [2, 1, 7, 3, 8, 9], n_days=4 (задача Б)
    task_reverse = Find_first_day_candidates(task_complexity_list[max_complexity_index:][::-1], n_days)
    print('\n Ответы задачи Б:', task_reverse)
        
    group_forward = {}
    for seq in task_forward:
        group_forward.setdefault(len(seq),[])
        group_forward[len(seq)] += [seq];   
    print('\n Сгруппированные по количеству дней ответы группы А:', group_forward) 
    
    group_reverse = {}
    for seq in task_reverse:
        group_reverse.setdefault(len(seq),[])
        group_reverse[len(seq)] += [seq[::-1]];    
    print('\n Сгруппированные по количеству дней ответы группы Б + реверс:', group_reverse)
    
    group_forward_leaders = {}
    for days, sequences in group_forward.items():
        group_forward_leaders[days] = sequences[0]
        for seq in sequences[1:]:
            if sum(seq) < sum(group_forward_leaders[days]):
                group_forward_leaders[days] = seq
    print('\n Лидеры группы А:', group_forward_leaders)
    
    group_reverse_leaders = {}    
    for days, sequences in group_reverse.items():
        group_reverse_leaders[days] = sequences[0]
        for seq in sequences[1:]:
            if sum(seq) < sum(group_reverse_leaders[days]):
                group_reverse_leaders[days] = seq    
    print('\n Лидеры группы Б', group_reverse_leaders)
    
    final_candidates = []
    for days, seq in group_forward_leaders.items():
        if (n_days-days+1 in group_reverse_leaders):
            final_candidates.append(seq[:-1] + group_reverse_leaders[n_days-days+1])
    print('\n Окончательные кандидаты:', final_candidates)
    
    win_count = sum(final_candidates[0])
    winner = final_candidates[0]
    for candidate in final_candidates[1:]:
        if sum(candidate) < win_count:
            win_count = sum(candidate)
            winner = candidate
    print('\n Победитель:', winner)
    return

Amazon_calc([3, 1, 4, 5, 9, 8, 3, 7, 1, 2], 4)

Amazon_calc([9,1,2,3,4,5,8], 4)

import math
from functools import lru_cache
from typing import Tuple, List
 
TSection = Tuple[int, int]
 
def solve(tasks: List[int], days: int) -> Tuple[int, List[TSection]]:
    @lru_cache
    def day_value(start: int, end: int) -> int:
        if end < start:
            return -math.inf
        return max(tasks[end], day_value(start, end - 1))
 
    @lru_cache
    def best_variant(start: int, days: int) -> Tuple[int, List[TSection]]:
        if start >= len(tasks):
            return math.inf, []
 
        if days <= 1:
            end = len(tasks) - 1
            return day_value(start, end), [(start, end)]
 
        variants = []
        for end in range(start, len(tasks)):
            value, descriptions = best_variant(end + 1, days - 1)
            new_value = day_value(start, end) + value
            new_descriptions = [(start, end)] + descriptions
            new_variant = new_value, new_descriptions
            variants.append(new_variant)
        return min(variants)
 
    return best_variant(0, days)

def print_solve(tasks: List[int], days: int) -> None:
    print(f'Tasks={tasks} Days={days}')
    print(f'Solve:')
    value, descriptions = solve(tasks, days)
    for start, end in descriptions:
        section = tasks[start: end + 1]
        print(f'Day {section} => max is {max(section)}')
    print(f'Total = {value}\n')
 
print_solve([3, 1, 4, 2, 5], 2)
print_solve([2, 4, 7, 3, 5, 1, 6], 3)
print_solve([3, 1, 4, 5, 9, 8, 3, 7, 1, 2], 4)
print_solve([1, 2, 3, 4, 5, 6, 7], 3)
print_solve([9, 1, 2, 3, 4, 5, 8], 4)

import math
from typing import Tuple, List
 
TSection = Tuple[int, int]
 
def solve(tasks: List[int], days: int) -> Tuple[int, List[TSection]]:
    n = len(tasks)
    d = [[0 for i in range(n)] for j in range(n)]
    v = [[(0, []) for i in range(n)] for j in range(n)]
 
    def day_value(start: int, end: int) -> int:
        if end < start:
            return -math.inf
        if d[start][end] != 0:
            return d[start][end]
        
        res = max(tasks[end], day_value(start, end - 1))
        d[start][end] = res
        return res
 
    def best_variant(start: int, days: int) -> Tuple[int, List[TSection]]:
        if start >= len(tasks):
            return math.inf, []
        if v[start][days] != (0, []):
            return v[start][days]
 
        if days <= 1:
            end = len(tasks) - 1
            return day_value(start, end), [(start, end)]
 
        variants = []
        for end in range(start, len(tasks)):
            value, descriptions = best_variant(end + 1, days - 1)
            new_value = day_value(start, end) + value
            new_descriptions = [(start, end)] + descriptions
            new_variant = new_value, new_descriptions
            variants.append(new_variant)
        
        res2 = min(variants)
        v[start][days] = res2
        return res2
 
    res3 = best_variant(0, days)
    print(f'd:')
    for k in range(n):
        print(f'{d[k]}')
    print(f'v:')
    for k in range(n):
        s = list(map(lambda x: x[0], v[k]))
        print(f'{s}')
    return res3
    
    
def print_solve(tasks: List[int], days: int) -> None:
    print(f'Tasks={tasks} Days={days}')
    print(f'Solve:')
    value, descriptions = solve(tasks, days)
    for start, end in descriptions:
        section = tasks[start: end + 1]
        print(f'Day {section} => max is {max(section)}')
    print(f'Total = {value}\n')
    
    
print_solve([2, 2, 2, 4, 1, 1, 1, 3], 4)

import math
from typing import Tuple, List
 
TSection = Tuple[int, int]
    
def solve(tasks: List[int], days: int) -> Tuple[int, List[TSection]]:
    n = len(tasks)
    m = n - days + 1
 
    d = [tasks]    
    for i in range(1, n):
        r = [max(d[i-1][j], d[i-1][j+1]) for j in range(n-i)]
        d.append(r)
 
    v = [[(0, []) for j in range(m)] for i in range(days)]
    for j in range(0, m):
        i = 0
        start = days - i - 1 + j
        k = n - 1 - start
        v[i][j] = d[k][start], [(start, start + k)]
    for i in range(1, days):
        for j in range(0, m):
            start = days - i - 1 + j
            variants = []
            for k in range(0, m - j):
                value, descriptions = v[i-1][j+k]
                new_value = d[k][start] + value
                new_descriptions = [(start, start + k)] + descriptions
                new_variant = new_value, new_descriptions
                variants.append(new_variant)
            res2 = min(variants)
            v[i][j] = res2
 
    print(f'd:')
    for k in range(n):
        print(f'{d[k]}')
 
    print(f'v:')
    for k in range(days):
        s = list(map(lambda x: x[0], v[k]))
        print(f'{s}')
 
    return v[days-1][0]
    
def print_solve(tasks: List[int], days: int) -> None:
    print(f'Tasks={tasks} Days={days}')
    value, descriptions = solve(tasks, days)
    print(f'Solve:')
    for start, end in descriptions:
        section = tasks[start: end + 1]
        print(f'Day {section} => max is {max(section)}')
    print(f'Total = {value}\n')
 
 
print_solve([2, 2, 2, 4, 1, 1, 1, 3], 4)

def solve(tasks: List[int], days: int) -> Tuple[int, List[TSection]]:
    @lru_cache
    def best_variant(start: int, days: int) -> Tuple[int, List[TSection]]:
        if days <= 0:
            return 0 if start >= len(tasks) else math.inf, []
 
        variants = []
        day_value = -math.inf
        for end in range(start, len(tasks) - days + 1):
            day_value = max(day_value, tasks[end])
            value, descriptions = best_variant(end + 1, days - 1)
            variant = value + day_value, [(start, end)] + descriptions
            variants.append(variant)
        return min(variants)
 
    return best_variant(0, days)