максимальная сумма элементов подмассива в массиве

[Sparky]

Доброе время суток, ребята дана такая задача. Дан массив размерности N нужно найти максимальную сумму элементов подмассива в массиве.

[ОДИНОЧЕСТВО В СЕТИ]

язык укажите

Идея алгоритма: вначале ищем первый положительный элемент в последовательности. Если такого не окажется, то наибольший из просмотренных и будет решением. Если такой элемент нашелся, то считаем, что текущая сумма и максимальная равны этому элементу. Начинаем просматривать эту последовательность до конца. На каждом шаге увеличиваем текущую сумму на текущий элемент. Если текущая сумма оказаласть отрицательной - зануляем ее. Кроме того, если значение текущей суммы окажется больше максимальной, то максимальную сумму считаем равной текущей.

[Sparky]

Обычный Pascal

[ОДИНОЧЕСТВО В СЕТИ]

var min,j,maxsum,sum,n: longint;
    inp, outp: text;
begin
  assign(inp,'input.txt');
  reset(inp);
  readln(inp);
  read(inp,min);
  while (not eof(inp))and(min<=0)do
  begin
    read(inp,j);
    if j>min then min:=j;// ищем первый  положительный элемент
  end;
  maxsum:=min; // максимальной сумме присваиваем значение первого положительного элемента
  sum:=min;     // тек сумме присваиваем значение максимального элемента
  while not eof(inp) do  //считываем посл-ть
  begin
    read(inp,j);   
     inc(sum,j);   // увеличиваем тек сумму на элемент посл-ти
    if sum>maxsum then maxsum:=sum; // если тек сумма> max суммы то максСумме := текСумму
    if sum<0 then sum:=0;// если ТекСумма<0 то обнуляем ее
  end;
  assign(outp,'output.txt');
  rewrite(outp);
  write(outp,maxsum); ну и выводим макс сумму
  close(inp);
close(outp);
end.

из найденного!
вариант на С++(или "си два плюса"-как говаривал мой препод по информатике в школе)

#include <stdio.h>

//int arr[]={-1, 3, -5, 3, 3, -8, 4, 7, -2, 3};
int arr[]={1, 7, -5, 3, -5, 9};

struct subsum
{
  int pos;
  int len;
  int sum;
} max, max_end;

int main(int argc, char** argv)
{
  int i, s;
  max_end.pos=0; max_end.len=1; max_end.sum=arr[0];
  max=max_end;
  for (i=1; i<(sizeof(arr)/sizeof(arr[0])); ++i)
  {
    s=arr;
    max_end.sum+=s; ++max_end.len;
    if (max_end.sum<s)
    {
      max_end.pos=i; max_end.len=1; max_end.sum=s;
    }
    if (max_end.sum>max.sum) max=max_end;
  }
 
  printf("Max. sum=%d has subarray (%d", max.sum, arr[max.pos]);
  for (i=max.pos+1; i<max.pos+max.len; ++i)
  {
    printf(", %d", arr);
  }
  printf(")\n");
}

[LeBron]

ОДИНОЧЕСТВО В СЕТИ, все верно, только еще нужно уточнение от автора - часто в этой задаче считают пустой подмассив одним из возможных вариантов, тогда надо выводить или положительное число, или 0 (если в массиве нету положительных элементов, то пустой подмассив и будет ответом). Если сдесь имеется ввиду непустой массив - тогда так. Иначе - пусть автор темы переделывает под себя.

[Sparky]

мне нужен был только сам алгоритм, под себя я его подстрою, еще раз спасибо, а можном алгоритм пояснить

[ОДИНОЧЕСТВО В СЕТИ]

можном алгоритм пояснить

добавила комментарии к посту №4

[Sparky]

если нет положительного то почему максимальный из просмотренных будет ответом?

[ОДИНОЧЕСТВО В СЕТИ]

если нет положительного то почему максимальный из просмотренных будет ответом?

потому что если все отрицательные или 0 то максимум из них и будет максимальной суммой так как вы просмотрите все элементы!

[Sparky]

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