Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Максимальный подмассив массива

Автор: 46&two 18.11.2004, 18:10

Решения этой (распространенной видимо) задачи на alglib я не нашел.
Зaдача такая:
есть массив целых (положительных и отрицательных) чисел A длиной N.
Нужно найти такие m и k, что A[m] + A[m+1] + .... A[m+k] максимально.
При этом построенный алгоритм должен иметь вычислительную сложность O(N).
Есть ли какие мысли?

Автор: val 18.11.2004, 19:21

Подумал и пришел к тому, что минимальное кол-во операций порядка n*k. Лучше не придумал. Если такое решение подходит, напишу алгоритм...

Автор: maxim1000 18.11.2004, 20:26

когда мне пришел в голову этот алгоритм, я попытался объяснить его коллеге и вдруг понял, что перевести его на C++ мне оказалось легче, чем на русский smile

Код


#include <iostream.h>

int array[]={2,-3,14,-1,2,-3,2,-15,5,-1,6,-1,12};
int maxend,maxbegin,maxsum;
void main()
{
  int end,begin,sum;
  maxend=1;
  maxbegin=0;
  maxsum=array[0];
  end=0;
  begin=0;
  sum=0;
  while(end<=sizeof(array)/4)
  {
    //try to shift begin
    if(sum<0)
    {
      begin=end;
      sum=0;
    }
    //shift end
    end++;
    sum+=array[end-1];
    if(sum>maxsum)
    {
      maxend=end;
      maxbegin=begin;
      maxsum=sum;
    }
  }
  cout<<maxbegin<<"\n";
  cout<<maxend-1<<"\n";
  cout<<maxsum<<"\n";
}

но все-таки немного пояснений:
есть два отрезка: текущий и оптимальный
у каждого отрезка есть два маркера: начальный и конечный
сначала текущий отрезок состоит только из одного элемента (первого)
потом начинаем двигаем правый маркер (и соответственно прибавляем элементы, которые встречаем, к текущей сумме) на один
на каждом шаге сравниваем текущий отрезок с оптимальным, если лучше - переписываем
после этого на каждом шаге проверяем не стала ли сумма по отрезку меньше нуля
если это так, то этот отрезок только испортит ситуацию в будущем, поэтому отрезаем его и делаем begin=end
в конце получаем оптимальный отрезок...

Автор: 46&two 19.11.2004, 09:07

maxim1000, а что будет, если все элементы массива отрицательны? не получится ли max = a[0]?

Автор: val 19.11.2004, 11:11

Программа выдаёт:
8
13
31

К сожалению, у нас нет 13-ого элемента...

В контекте данного решения надо выводить end - 2? то есть:

Код


  cout<<maxend-2<<"\n";

Ну сумма, наверно должна быть 5 + (-1) + 6 +(-1) + 12 = 21.
Что не сходится...
Если все числа отрицательны, то программа, к сожалению, выдаёт совсем не то, что надо... smile

Прошу прощения за критику... smile

Автор: maxim1000 19.11.2004, 11:54

Цитата(46 @ 19.11.2004, 08:07)

maxim1000, а что будет, если все элементы массива отрицательны? не получится ли max = a[0]?

согласен...
просто надо сначала пройтись по массиву и найти максимальный элемент
если он отрицательный - вывести его и выйти
на порядок сложности это не повлияет

Цитата(val @ 19.11.2004, 10:11)

К сожалению, у нас нет 13-ого элемента...

честно говоря, не понял...
где нет 13-го элемента?

Цитата(val @ 19.11.2004, 10:11)

В контекте данного решения надо выводить end - 2? то есть:

в этой программе за end принято номер первого элемента справа от отрезка, т.е. отрезок на самом деле является полуинтервалом: [begin;end), а если нужно описать конец отрезка, нужно отнять 1...

Цитата(val @ 19.11.2004, 10:11)

Прошу прощения за критику...

если бы мне не была интересна критика этой программы, я бы, наверное, и не выкладывал ее smile

Автор: val 19.11.2004, 12:01

Цитата

честно говоря, не понял...
где нет 13-го элемента?

На вопрос ответил ниже:

Цитата

отрезок на самом деле является полуинтервалом: [begin;end), а если нужно описать конец отрезка, нужно отнять 1...

Автор: manu 19.11.2004, 12:12

int a[10]={...},n;

struct A {
int begin,end,sum;
};

// 1. если все элементы не положительны, то искомый отрезок -- максимальный элемент a
bool check() {
int i, maxval,maxpos;

for(i=0; i<n; i++) if(a[n]>0) return false;

max=a[0];
for(i=1; i<n; i++) if(a[i]>max) {
max=a[i];
}

// 2. считаем суммы положительных и отрицательных отрезков

int

Автор: 46&two 19.11.2004, 13:41

manu, будь добр, заверши идею. smile

Автор: val 22.11.2004, 13:40

maxim1000 с такими входными данными твоя программка не работает...

Код


int array[]={-5, -1, 2, 4, -16};

Автор: maxim1000 22.11.2004, 14:13

Цитата(val @ 22.11.2004, 12:40)

maxim1000 с такими входными данными твоя программка не работает...

не знаю, у меня выдает 2, 3, 6

Автор: manu 22.11.2004, 14:33

Цитата(46 @ 19.11.2004, 13:41)

manu, будь добр, заверши идею. smile

я начал писать, потом понял, что мое решение не подходит, а сообщение почему-то запостилосьЖ)
я думаю, что когда мы двигаем начало, то надо двигаться не на длину всего отрезка, а на 1 позицию.

Автор: val 22.11.2004, 15:53

Код


#include <iostream.h>

int array[]={-5, -1, 2, 4, -16};
int maxend,maxbegin,maxsum;
void main()
{
 int end,begin,sum;
 maxend=1;
 maxbegin=0;
 maxsum=array[0];
 end=0;
 begin=0;
 sum=0;
 while(end<=sizeof(array)/4)
 {
   //try to shift begin
   if(sum<0)
   {
     begin=end;
     sum=0;
   }
   //shift end
   end++;
   sum+=array[end-1];
   if(sum>maxsum)
   {
     maxend=end;
     maxbegin=begin;
     maxsum=sum;
   }
 }
 cout<<maxbegin<<"\n";
 cout<<maxend-1<<"\n";
 cout<<maxsum<<"\n";
}

У меня этот код выдаёт
5,
5,
10

Автор: maxim1000 22.11.2004, 17:23

я специально скопировал код в новый проект: 2,3,6
у меня VisualStudio 6.0, а у тебя?

Автор: val 22.11.2004, 17:49

Цитата

я специально скопировал код в новый проект: 2,3,6
у меня VisualStudio 6.0, а у тебя?

Visual Studio. NET 7.0.

Автор: maxim1000 22.11.2004, 18:19

попробуй вместо sizeof(array)/4 вручную записать количество элементов
(а то у меня такое ощущение, что происходит выход за границы массива)

Автор: val 22.11.2004, 19:03

Поменял, нет не работает. Ладно, с логикой всё Ок, это главное... smile

Автор: 3,14 22.11.2004, 22:33

Собственно- вот мой вариант (необессудьте на опечатки, код не тестил, пишу на вскидку):

Код


int max_ k = k = 1;
int max_sum = sum = a[0];
int max_m = m = 0;
for(int j = 1; j < n; j++)
{
  if (sum < 0)
  {
     sum = a[j];
     m = j;
     k = 1;
  }
  if (a[j] < 0)
  {
     if (sum > max_sum)
     {
        max_sum = sum;
        max_k = k
        max_m = m;
     }
     sum = <САМОЕ МАЛЕНЬКОЕ ИЗ ДОПУСТИМЫХ>;
  }
  else
  {
     sum += a[j];
     k++;
  }
}
if (sum > max_sum)
{
   max_sum = sum;
   max_k = k
   max_m = m;
}
//вывод

Вроде должно работать