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

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

Это сообщение отредактировал(а) val - 18.11.2004, 19:23

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

Код

#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
в конце получаем оптимальный отрезок...

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

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


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

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

Код

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

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

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

Это сообщение отредактировал(а) val - 19.11.2004, 11:13

Цитата(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)

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

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

Это сообщение отредактировал(а) maxim1000 - 19.11.2004, 11:55

Цитата

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

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

Цитата

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

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

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

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

Код

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

Это сообщение отредактировал(а) val - 22.11.2004, 13:41

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

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

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

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

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

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

Код

#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

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

Цитата

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

Visual Studio. NET 7.0.

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

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

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

Код

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; } //вывод

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

Это сообщение отредактировал(а) 3,14 - 22.11.2004, 22:46