Наибольшая сумма всех смежных подмассивов

Question

У меня есть упражнение, чтобы решить: "Напишите эффективную программу на C, чтобы найти наибольшую сумму смежных подмассивов в одномерном массиве целых чисел. Непрерывный подмассив массива определяется как последовательность элементов, которые находятся в любом непрерывном наборе индексы, которые действительны в массиве.

Давайте возьмем пример массива {5,-3, 4}. Возможные смежные комбинации подмассивов: {5}, {-3}, {4}, {5,-3}, {-3,4} и {5, -3,4}. Обратите внимание, что {5,4} не является допустимым подмассивом, так как индексы 5 и 4 не являются непрерывными. Смежный подмассив {5, -3,4} имеет наибольшую сумму 6 ".

Я пытался решить ее, но понял, что даже не понял проблемы, поскольку, если у меня есть массив из 5 разных значений, результат должен быть 10, тогда как я бы сказал 15 (5 разных элементов + 1 в целом + 4 элемента если взято 2 на 2 + 3, если взято 3 на 3 + 2, если взято 4 на четыре).

Прежде чем пытаться закодировать его (в C), я хотел бы знать, может ли кто-нибудь помочь мне понять саму проблему.

Answer 1

Вот как бы я решил проблему. Это не обязательно оптимальное решение, но я считаю, что оно должно работать.

Рассмотрим массив: {1, -2, 3, 5, -4} и рассмотрим, как вы можете написать все вложенные массивы вручную:

1. начать с массива из 5 элементов: {1, -2, 3, 5, -4} сумма: 3
   
2. затем выписать 4-элементные массивы:
   {1, -2, 3, 5} сумма: 7
   {-2, 3, 5, -4} сумма: 2
   
3. продолжить с 3-элементными массивами:
   {1, -2, 3} сумма: 2
   {-2, 3, 5} сумма: 6
   {3, 5, -4} сумма:4
   
4. Теперь 2-элементные массивы:
   {1, -2} сумма: -1
   {-2, 3} сумма: 1
   {3, 5} сумма: 8
   {5, -4} сумма: 1
   
5. наконец, 1-элементные массивы:
   {1} сумма: 1
   {-2} сумма: -2
   {3} сумма: 3
   {5} сумма: 5
   {-4} сумма: -4
   

Похоже, самая большая сумма 8.

Здесь вы должны увидеть шаблон, который я начал с длины массива, в данном случае 5, и уменьшил ее на единицу, пока не обработал одноэлементные массивы. Я также начал с нулевого элемента массива и попытался создать правильный массив с учетом длины. Например, если бы я работал с массивами из четырех элементов, начиная с элемента массива 0, он мог бы создать подмассив с помощью массивов [0] -> массив [3] и массив [1]-> массив [4] (это нарезка массива, некоторые языки, такие как Python, имеют явное обозначение для выполнения среза массива, C - нет). После генерации каждого среза, суммируйте элементы, когда закончите, ищите макс.

Теперь я бы написал это примерно так

int main(void)
{
    int array[] = {1, -2, 3, 5, -4};
    int max = -1;                         // will hold largest sum
    int len = sizeof(array)/sizeof(int);  // C-idiom to find length of array

    for(int slen = len; slen > 0; slen--)           // loop for length of sub-arrays
    {
        for(int jdx = 0; jdx+slen <= len; jdx++)   // looping over elements in original array
        {
             int temp = calcSum(array, jdx, slen);
             if(temp > max)
                 max = temp;

        }
    }
    printf("maximum sum of sub-array is: %d\n", max);
}

Теперь все, что осталось, это написать calcSum функция. Он принимает три параметра: первый - это исходный массив, второй - где начинается вложенный массив, а это - длина вложенного массива.

int calcSum(int* array, int start, int len)
{
    int    sum = 0;
    printf("[%d:%d]: {", start, start+len);
    for(int ndx = 0; ndx < len; ndx++)
    {
        printf("%d,", array[start+ndx]);
        sum = sum + array[start+ndx];
    }

    printf("} the sum is %d\n", sum);
    return sum;
}

Я добавил туда несколько printf, чтобы вы могли видеть, что происходит, когда программа зацикливается. Моя запись среза - [start:length], поэтому [1:3] будет массивом, который начинается с первого индекса и имеет длину 3 (т.е. array[1], array[2], array[3]).

Компиляция выше как gcc -std=c99 -pedantic -Wall test.c -o temp и выполняя это, дает:

D:\Users\******\GNUHome>temp.exe
[0:5]: {1,-2,3,5,-4,} the sum is 3
[0:4]: {1,-2,3,5,} the sum is 7
[1:4]: {-2,3,5,-4,} the sum is 2
[0:3]: {1,-2,3,} the sum is 2
[1:3]: {-2,3,5,} the sum is 6
[2:3]: {3,5,-4,} the sum is 4
[0:2]: {1,-2,} the sum is -1
[1:2]: {-2,3,} the sum is 1
[2:2]: {3,5,} the sum is 8
[3:2]: {5,-4,} the sum is 1
[0:1]: {1,} the sum is 1
[1:1]: {-2,} the sum is -2
[2:1]: {3,} the sum is 3
[3:1]: {5,} the sum is 5
[4:1]: {-4,} the sum is -4
maximum sum of sub-array is: 8

NB Я скомпилировал это с gcc версии 4.8.3 (от mingw) на Windows 7 Professional.