Учитывая массив чисел, найдите число, с которого нужно начать, чтобы сумма никогда не была отрицательной.

Учитывая массив целых чисел, найдите наименьшее число X для начала, такое, что при добавлении элементов массива к X сумма всегда больше 0

Если задан массив {-2, 3, 1, -5} Например, в приведенном выше массиве X должно быть 4

Объяснение: если мы начинаем с 4, то добавляем первое число -2, сумма массива становится равной 4 + (-2) = 2 (то есть> 0). Теперь добавляем следующий элемент 3 к текущей сумме, которая равна 2, 2+ 3 = 5 (что > 0) Добавление следующего элемента 1 к новой сумме 5 дает 5 + 1 = 6 (что > 0) Добавление последнего элемента -5 к новой сумме 6 дает 6 + (-5) = 1, что снова больше чем ноль.

Учитывая массив целых чисел, как я могу найти наименьшее число X?


arrays algorithm array-algorithms
person Himanshu Saxena    schedule 19.05.2020    source источник
comment
Может ли X быть отрицательным? Например. данный массив может быть {2}, поэтому X = -1 будет работать.   -  person Andrew Morton    schedule 19.05.2020
comment
@AndrewMorton, да, X тоже может быть отрицательным   -  person Himanshu Saxena    schedule 20.05.2020

Ответы (4)


arrow_upward
2
arrow_downward

Найдите минимум кумулятивной суммы для заданного массива.
Требуемый результат: 1 - MinC

A = [-2, 3, 1, -5]
CSum = 0
MinC = 10000000000
for x in A:
    CSum += x
    MinC = min(MinC, CSum)
Addend = 1 - MinC
print(Addend)

>>> 4
person MBo    schedule 20.05.2020
comment
Проголосовал. Спасибо. Я также хотел узнать, как вы решаете эту проблему, если можете. - person Himanshu Saxena; 28.05.2020
comment
Я видел, что вы описали кумулятивную сумму, и ее минимум точно соответствует нужному значению. Просто посмотрите на свою сумму без мы начнем с 4 - person MBo; 28.05.2020

arrow_upward
1
arrow_downward

Сначала мы должны проверить, больше ли элемент в позиции ith нуля или нет. Если элемент больше нуля, то нет проблем, и мы можем добавить его непосредственно к нашей сумме, ans остается неизменным. Но если не больше нуля, то мы сначала проверяем, больше ли сумма элемента или нет. Если сумма больше abs(arr[I]), то мы уменьшаем нашу сумму на abs(arr[I]), ans остается неизменной, но если abs(arr[I]) больше суммы, мы добавляем abs(arr[i]-sum+1) к ans и инициализируем сумму 1.

Ниже приведен код для того же:

 #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
        // considering x>=0(x can't take values less than 0)
        ll arr[] = { -2, 3, 1, -5};
        ll n = sizeof(arr) / sizeof(ll);
        ll ans = 0; // My answer
        ll sum = 0; // current sum of elements
        for (ll i = 0; i < n; i++)
        {
            if (arr[i] <= 0)
            {
                if ((sum + arr[i]) <= 0)
                {
                    ans += (abs(sum + arr[i]) + 1); //add 1 to make sum=1
                    sum = 1;
                }
                else
                    sum += arr[i];   // added because arr[i]<=0,(sum-=abs(arr[i]))
            }
            else
                sum += arr[i];
        }
        cout << ans;

        return 0;
    }
    // ans=4 for this case
person Vishal_898    schedule 20.05.2020
comment
Что произойдет, если все элементы положительны? Это не вернет минимальное число. - person Himanshu Saxena; 21.05.2020
comment
Я, вот почему я прокомментировал, что ответ больше или равен 0. Означает, что если все положительные, мой ответ будет 0 - person Vishal_898; 23.05.2020

arrow_upward
0
arrow_downward

вы должны сначала найти минимальную сумму подмассива. скажем, он равен k. ваш ответ должен быть k+1. вы можете найти минимальную сумму здесь: сумма смежных подмассивов/

person Mr Sukhe    schedule 19.05.2020

arrow_upward
0
arrow_downward

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

Найдите сумму всех элементов, присутствующих в массиве.

Если сумма равна нулю, верните 1, так как это даст наименьшее число, при сложении которого мы получим общую сумму больше нуля.

Если сумма больше нуля, вернуть отрицательное число, чуть меньше этой суммы ( обрабатывать особый случай суммы == 1 отдельно)

Если сумма отрицательна, верните положительное число только на единицу больше, чем сумма по величине.

Шаг 1. Найдите сумму всех элементов массива.

 int sum = 0;
for(int i = 0; i < arr.size(); i++)
 {
         sum += arr[i];
 }

Шаг 2. Проверьте полученную сумму и примените следующую логику.

if(sum == 0)
         return 1;
else if( sum < 0)
         return abs(sum)+1;
else 
        {
               if( sum == 1)
                          return 0;
               else
                         return  -(sum-1);

         }
person Prajjwal Pandey    schedule 24.05.2021