Как найти максимальную сумму не кратную 5

Задача, на самом деле, не совсем логична. Ведь, давайте представим такой массив:

 int a[16] = {-6,2,5,1,0,3,4,5,8,8,10,9,11,23,14,25};

Ведь его можно разделить всего на две части: первые два числа и все остальное. При чем все остальное — есть непрерывная последовательность, сумма элементов которой больше суммы первой подгруппы. Так можно делать с каждым массивом: тупо бить его на две или три части последовательно. Подумайте сами. Задача либо требует уточнений( например, максимальное количество элементов в последовательности ), либо не верна.

К примеру, я придумал такой алгоритм( Работа алгоритма производится за линейное время. Это придает алгоритму краткость и понятность. ):

(Алгоритм основан на том, что каждое отрицательное значение дает минус в сумме подгруппы )

int sums[16] = {0};
int a[16] = {-6,1,-2,0,1,1,-17,1,0,1,-100,1,1,-1,-1,1};
int n = 0;
for(int i = 0;i<16;i++)
{
    if(a[i]>=0)
    for(int j=n;j<=i;j++) sums[j]+=a[i];
    else n=i;
}
int max = 0; int ind = 0;
for(int j=0;j<16;j++)
{
    cout<<sums[j]<<endl;
    if(sums[j]>max) {max = sums[j]; ind=j;} 
}

cout<<"The longest subarray in array begins in "<<ind+1<<" position! Sum  =  "<<max<<endl;

Задачка была следующая — дан массив длинной до 200, 000 элементов, элементами которого являются целые числа в диапазоне [-10000, 10000].
Нужно найти максимальную сумму, которую можно получить сложением произвольной неразрывной последовательности элементов этого массива.
Типа для входных данных [2,-2,-5,2,2,-1,2,-3] будет 5 — сумма подмассива [2,2,-1,2]

Я в алгоритмах не силен, но вроде как нащупал верный, правда забыл про смешное граничное условие и не успел закончить вовремя.

Как бы вы стали решать эту задачу?
В условии также есть ограничение по времени выполнения алгоритма — не более 2-х секунд в их интерпретаторе.

Напишите программу, которая в последовательности натуральных чисел определяет
максимальное число, кратное 5. Программа получает на вход количество чисел в
последовательности, а затем сами числа. В последовательности всегда имеется
число, кратное 5. Количество чисел не превышает 1000. Введённые числа не превышают
30 000. Программа должна вывести одно число – максимальное число, кратное 5.

Пример работы программы:

var i, n, a, max: integer; /объявление переменных

begin

max:=0; /начальное значение max

readln(n); /ввод количества чисел в последовательности

for i:=1 to n do /цикл 

begin

readln(a); /ввод числа

if (a mod 5=0) and (a>max) then max:=a; /проверка условия и нахождение max

end;

writeln(max); /вывод найденного максимального кратного 5

Задача 2

Напишите программу, которая в последовательности натуральных чисел определяет
сумму чисел, кратных 6. Программа получает на вход количество чисел в
последовательности, а затем сами числа. В последовательности всегда имеется число,
кратное 6. Количество чисел не превышает 100. Введённые числа не превышают 300.
Программа должна вывести одно число – сумму чисел, кратных 6.

Пример работы программы:

Пояснение: в данной программе будем использовать переменные n — количество чисел в последовательности, s — для хранения найденной суммы, k — переменная цикла, g — вводимое число. 
Мы ищем сумму, поэтому начальное значение s:=0. 
Условие отбора кратность 6  (g mod 6=0)
Текст программы

var n, s, k, g:
integer; /объявление переменных

begin

s:=0; /начальное значение суммы чисел

readln(n); /ввод количества чисел в последовательности

for k:=1 to n do /цикл

begin

readln(g); /ввод числа

if (g mod 6=0) then s:=s+g; /проверка условия и нахождение суммы

end;

writeln(s); /вывод суммы чисел кратных 6

Задача 3

Напишите программу, которая в последовательности натуральных чисел определяет
количество чисел, кратных 4. Программа получает на вход количество чисел в
последовательности, а затем сами числа. В последовательности всегда имеется
число, кратное 4. Количество чисел не превышает 1000. Введённые числа не превышают
30 000. Программа должна вывести одно число – количество чисел, кратных 4.

Пример работы программы:

Пояснение: в данной программе будем использовать переменные n — количество чисел в последовательности, s — для хранения количества чисел кратных 4, k — переменная цикла, g — вводимое число. 
Мы ищем количество, поэтому начальное значение s:=0. 
Условие отбора кратность 4  (g mod 4=0)
Текст программы

var n, s, k, g:
integer; /объявление переменных

begin

s:=0; /начальное значение количества чисел кратных 4

readln(n); /ввод количества чисел в последовательности

for k:=1 to n do /цикл

begin

readln(g); /ввод числа

if (g mod 4=0) then s:=s+1; /проверка условия и нахождение количества

end;

writeln(s); /вывод количества чисел кратных 4

Задача 4

Напишите программу, которая в последовательности натуральных чисел определяет
количество чисел, оканчивающихся на 3. Программа получает на вход количество
чисел в последовательности, а затем сами числа. В последовательности всегда имеется
число, оканчивающееся на 3. Количество чисел не превышает 1000. Введённые числа
не превышают 30 000. Программа должна вывести одно число – количество чисел,
оканчивающихся на 3.

Пример работы программы:

Пояснение: в данной программе будем использовать переменные n — количество чисел в последовательности, s — для хранения количества чисел оканчивающихся на 3, k — переменная цикла, a — вводимое число. 
Мы ищем количество, поэтому начальное значение s:=0. 
Условие число оканчивается на 3  (a mod 10=3)
Текст программы

var n, s, k, a:
integer; /объявление переменных

begin

s:=0; /начальное значение количества чисел оканчивающихся на 3

readln(n); /ввод количества чисел в последовательности

for k:=1 to n do /цикл

begin

readln(a); /ввод числа

if (a mod 10=3) then s:=s+1; /проверка условия и нахождение количества

end;

writeln(s); /вывод количества чисел оканчивающихся на 3

Задача 6

Напишите программу, которая в последовательности натуральных чисел определяет
определяет сумму всех чисел, кратных 6 и оканчивающихся на 4. Программа получает
на вход натуральные числа, количество введённых чисел неизвестно, последовательность
чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в
последовательность). Количество чисел не превышает 1000. Введённые числа не превышают
30 000. Программа должна вывести одно число: сумму всех чисел, кратных 6 и оканчивающихся
на 4.

Пример работы программы:

Пояснение: в данной программе будем использовать переменные a — вводимое число, s — для хранения суммы чисел кратных 6 и оканчивающихся на 4.
Мы ищем сумму, поэтому начальное значение s:=0. 
Условия: кратность 6 (a mod 6=0), число оканчивается на 4 (a mod 10=4)
Текст программы

var a, s: integer; /объявление переменных

begin

s:=0; /начальное значение суммы

readln(a); /ввод числа

while a<>0 do begin /оператор цикла пока а не равно 0

if (a mod 6=0) and (a mod 10=4) then s:=s+a; /проверка условий

readln(a); /ввод числа

end;

writeln(s); /вывод суммы чисел кратных 6 и оканчивающихся на 4

Задача 7

Напишите программу, которая в последовательности целых чисел определяет
количество нечётных чисел, кратных 3. Программа получает на вход целые числа,
количество введённых чисел неизвестно, последовательность чисел заканчивается
числом 0 (0 – признак окончания ввода, не входит в последовательность). Количество
чисел не превышает 1000. Введённые числа по модулю не превышают 30 000. Программа
должна вывести два числа: длину последовательности (завершающий 0 не
учитывается) и количество нечётных чисел, кратных 3.

Пример работы программы:

Пояснение: в данной программе будем использовать переменные a — вводимое число, k — для хранения количества нечетных чисел кратных 3, n длина последовательности (количество чисел введенных с клавиатуры не считая последний 0).
Мы ищем количество, поэтому начальное значение k:=0 и n:=0.
Условия: нечетность (a mod 2 <>0), кратность 3 (a mod 3=0)
Текст программы

var k, a, n:
integer; /объявление переменных
begin

n:=0; /начальное значение счетчика чисел в последовательности

k:=0; /начальное значение количества чисел удовлетворяющих условию отбора

readln(a); /ввод числа

while a<>0 do /оператор цикла пока а не равно 0
begin

n:=n+1; /подсчет количества чисел в последовательности

if (a mod 2<>0) and (a mod 3=0) then k:=k+1; /проверка условия

readln(a); /ввод числа

end;

writeln(n); /вывод количества чисел в последовательности
writeln(k); /вывод количества нечетных чисел кратных 3

Задача 8

Напишите программу, которая в последовательности натуральных чисел определяет
количество всех чётных чисел, кратных 5. Программа получает на вход натуральные
числа, количество введённых чисел неизвестно, последовательность чисел заканчивается
числом 0 (0 – признак окончания ввода, не входит в последовательность). Количество
чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна
вывести одно число: количество всех чётных чисел, кратных 5.

Пример работы программы:

Пояснение: в данной программе будем использовать переменные a — вводимое число, s — для хранения количества четных чисел кратных 5.
Мы ищем количество, поэтому начальное значение s:=0. 
Условия: четное число, кратное 5 это число оканчивается на 0 (a mod 10=0)
Текст программы

var a, s: integer; /объявление переменных

begin 
s:=0; /начальное значение количества

readln(a); /ввод числа

while a<>0 do /оператор цикла пока а не равно 0

begin

if a mod 10=0 then s:=s+1; /проверка условия

readln(a); /ввод числа

end;

writeln(s) /вывод количества четных чисел кратных 5

Задача 9

Напишите программу, которая в последовательности натуральных чисел определяет
сумму всех чисел, кратных 7 и оканчивающихся на 2. Программа получает на вход
натуральные числа, количество введённых чисел неизвестно, последовательность
чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в
последовательность). Количество чисел не превышает 1000. Введённые числа не превышают
30 000. Программа должна вывести одно число: сумму всех чисел, кратных 7 и оканчивающихся
на 2.

Пример работы программы:

Текст программы

var a, s: integer;

begin

s:=0;

readln(a);

while a<>0 do

begin

if (a mod 7=0) and (a mod 10=2) then s:=s+a;

readln(a);

end;

writeln(s);

Перейти к содержанию

import bisect

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        msum = 0
        n = len(nums)
        total = sum(nums)
        if total % 3 == 0:
            return total
        nums.sort()
        paths = [(nums[i], i) for i in range(n)]
        i = 0
        while i < len(paths):
            currsum, curr = paths[i]
            if (total - currsum) % 3 == 0:
                return total - currsum
            for j in range(curr + 1, n):
                bisect.insort(paths, (currsum + nums[j], j))
            i += 1
        return 0