największa suma algorytm?

0

Mam takie liczby 1, -2, 4, 5, -2 po opuszczeniu skrajnych liczb największa suma to 9
inny przykład -3, 1, -1, 1, -6, 3, 3, 3, -7, 20, 5, -1, -1 po opuszczeniu 5 skrajnych z lewej i 2 z skrajne z prawej można uzyskać największą sumę 27
inny przykład dla 4, 0, 0, 9 dla 13
inny przykład dla -1, -2 to 0
UWAGA! Można usuwać tylko skrajne liczby (zniwelować do takiego stopnia że po usunięciu tych liczb skrajnych suma pozostałych liczb da wartość większą niż ze skrajnymi liczbami które zostaną opuszczone)

Ma ktoś pomysł na algo w c++? Może jest jakaś gotowa funkcja?

0

Jest taka jedna metoda, niezawodna: BRUTE FORCE

Pseudokod:

max=suma wszystkich
maxX=0
maxY=n-1
for x: (0)..(n-1):
  for y: (n-1)..(x+1):
    oblicz sumę od tab[x] do tab[y] (włącznie)
    jeśli suma>max:
      max=suma ; maxX=x ; maxY=y
1

Scala:

object Main extends Application {
  val inputs = List(
    List(1, -2, 4, 5, -2),
    List(-3, 1, -1, 1, -6, 3, 3, 3, -7, 20, 5, -1, -1),
    List(4, 0, 0, 9),
    List(-1, -2))

  inputs.map(_.foldLeft((0, 0)) {
    case ((cur, max), value) =>
      val newCur = cur + value
      if (newCur < 0) (0, max) else (newCur, Math.max(newCur, max))
  }._2).foreach(println)
}

Java:

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        List<int[]> inputs = Arrays.asList(
                new int[]{ 1, -2, 4, 5, -2},
                new int[]{-3, 1, -1, 1, -6, 3, 3, 3, -7, 20, 5, -1, -1},
                new int[]{4, 0, 0, 9},
                new int[]{-1, -2});
        for (int[] input : inputs) {
            int max = 0;
            int cur = 0;
            for (int value : input) {
                cur = cur > -value ? cur + value : 0;
                max = max > cur ? max : cur;
            }
            System.out.println(max);
        }
    }
}

C++:
Nie chce mi się :P

Edit:
Albo jednak. Ale tylko dla jednej tablicy:

#include <cstdio>

int main() {
    int input[] = {-3, 1, -1, 1, -6, 3, 3, 3, -7, 20, 5, -1, -1};
    
    int cur = 0;
    int max = 0;
    for (int i = 0; i < sizeof(input) / sizeof(int); i++) {
        cur = cur > -input[i] ? cur + input[i] : 0;
        max = max > cur ? max : cur;
    }
    printf("%d\n", max); 
}
0

A może tak? Znaleźć miejsca wystąpienia pierwszej dodatniej (p) i ostatniej dodatniej (k) i sumować od p dok k. Jeśli żadnej dodatniej nie ma, to zwrócić 0.

0

Funkcja zwracająca ilość elementów do odrzucenia z każdej strony, optymalna, maksymalnie uproszczona, tym razem bez funkcyjnych udziwnień:

def calcDrops(data):
    if not data:
        return 0, 0

    minFromStartValue, minFromEndValue = data[0], data[-1]
    minFromStartIndex, minFromEndIndex = -1, len(data)
    
    fromStartIndex, fromEndIndex = 0, len(data) - 1
    fromStartValue, fromEndValue = 0, 0
    
    while fromEndIndex > fromStartIndex:
        fromStartValue += data[fromStartIndex]
        fromEndValue   += data[fromEndIndex]

        if fromStartValue < minFromStartValue:
            minFromStartValue = fromStartValue
            minFromStartIndex = fromStartIndex

        if fromEndValue < minFromEndValue:
            minFromEndValue = fromEndValue
            minFromEndIndex = fromEndIndex

        fromStartIndex += 1
        fromEndIndex   -= 1
    
    return minFromStartIndex + 1, len(data) - minFromEndIndex

Problem sprowadza się do znalezienia minimum sumy z każdej strony i odrzucenia wszystkiego do tego miejsca.

0

@Wibowit, chyba coś pomyliłeś, algorytm ma odrzucać skrajności, tj. wartości z obu stron.

0

bo:
Fail. Co dostaniesz dla ciągu:
8, -10, 8
?

0

Dobra, mój algorytm również można skreślić, źle warunek skonstruowałem, wyszukiwanie nie musi być symetryczne. Poza tym koncepcja i implementacja jest dobrze.

0

ofidydil:
No to przecież odrzuca w ten sposób. Chyba, że chodzi ci o obliczanie współrzędnych końców maksymalnego przedziału?

Algorytm on-line, Java:

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        List<int[]> inputs = Arrays.asList(
                new int[]{ 1, -2, 4, 5, -2},
                new int[]{-3, 1, -1, 1, -6, 3, 3, 3, -7, 20, 5, -1, -1},
                new int[]{4, 0, 0, 9},
                new int[]{-1, -2});
        for (int[] input : inputs) {
            int max = 0;
            int cur = 0;
            int curLeft = 0;
            int maxLeft = 0;
            int maxRight = -1;
            for (int i = 0; i < input.length; i++) {
                int value = input[i];
                if (cur > -value) {
                    cur += value;
                } else {
                    cur = 0;
                    curLeft = i + 1;
                }
                if (max < cur) {
                    max = cur;
                    maxLeft = curLeft;
                    maxRight = i;
                }
            }
            System.out.println(max + " " + maxLeft + " " + maxRight);
        }
    }
}
0

Tak sobie patrzę na ten kod w Scali i zastanawiam się, co będzie dla listy zawierającej same liczby ujemne? Czy w takim wypadku największą sumą elementów nie powinna być największa pojedyncza liczba?

0

Przepraszam, teraz doczytałem, że suma ma być nieujemna. Zdecydowanie za późno na algorytmy dla mnie, przepraszam, dobranoc.

0

Znaleźć najmniejszą sumę liczb od początku, znaleźć najmniejszą sumę od końca. To co zostaje jest wynikiem (zero jeśli oba przedziały się przecinają).

0

Mój nocny wynalazek (odrzucenie początkowych i końcowych liczb ujemnych i zsumowanie pozostałych) jest błędny. Można go zmodyfikować, znaleźć największą sumę pozostałych. Przypominam problem sprzed kilku miesięcy:
http://4programmers.net/Forum/Algorytmy/181674-maksymalna_suma_podtablicy_podprostokata_main?hl=suma.

0
def suma(tab):
  sum=0
  for a in tab:
    sum+=a
  return sum

def naj(arr):
  n=len(arr)
  maxX=0
  maxY=n
  max=0
  for x in range(n):
    for y in range(n-1, x, -1):
      w=suma(arr[x:y+1]) #Przekazuje wycinek tablicy, od komórki x do komórki y włącznie
      if max<w: 
        max=w
        maxX=x
        maxY=y
  print(str(maxX)+";"+str(maxY))
  return max
  
print(naj([-3, 1, -1, 1, -6, 3, 3, 3, -7, 20, 5, -1, -1]))
print(naj([1, -2, 4, 5, -2 ]))
print(naj([4, 0, 0, 9]))
print(naj([-1, -2]))

Rozwiązanie siłowe w Pythonie. Choć niezbyt optymalne, jest pewność że da dobre rozwiązanie :)

0

To python nie ma funkcji do sumowania tablicy? :P

"Siłowe" O(n^3), a moje ma złożoność O(n) :)

0

Jeśli dobrze zrozumiałem zadanie to w perełkach oprogramowania jest analogiczne.

Zadanie sprowadza się do dziel i zwyciężaj - mamy listę liczb 'm':
[ m ]

To funkcja f wyliczająca największą sumę działa tak że dzieli listę na 2 części:
[ a | b ]

i powtarzamy rekurencyjnie dla a i b do momentu kiedy do m należy tylko jeden element x. Wtedy wynikiem jest dla x <=0 -> zbiór pusty, a dla x > 0 po prostu { x }.

teraz największa suma jest w f(a) albo f(b) (albo ich części wspólnej), tak?
Nie, jeszcze może być pośrodku. Osiągamy to przez jechanie w lewo i prawo od środka 'ramionami' szukając największej sumy.

Złożoność O(n)O(n*log(n)), żadne n2 czy n3

Jak będę pamiętał to wrócę tu z książką i przepiszę implementację (wymyślanie jest podatne na błędy i męczące ;) ).

0

Ten algo o którym wspominasz ma złożoność O(n log n). Nie przyglądałem się za bardzo rozwiązaniu Wibowita, ale w Perełkach Bentley pokazuje taki algorytm (złożoność O(n))
pseudo kod przepisany z książki:

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)
0

Nie widziałem błędu w algorytmie @Wibovita, napisałem więc program testujący (losuje on pewną ilość tablic, liczy maksymalną sumę metodą Wibovita i metodą BruteForce. Porównuje wyniki i mierzy czas obliczeń. Przykładowe wyniki (tysiąc tablic, ilość liczb w każdej jest losowana z zakresu [5;1004], liczby są losowane z zakresu [-4;9]):
Rożne wyniki: 0
BruteForce(ms.): 161875
Wibovit(ms): 16

0

Takie łatwe a nikt nie umie wymyślić dobrego algorytmu, rotfl :/

0

A co rozumiesz pod pojęciem dobry? Może ktoś testuje na liczbach rzędu 21352957629843579234875. Wtedy na pewno mój algo nie przejdzie, bo dostanie przepełnienia.

0

Wibowit twój algo jest okey, tylko nie jest on optymalny

0
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;


const int size = 131072, infinity = 2000000000;

struct MinMax
{
	int min_value, max_value;

	explicit MinMax(int min_v = infinity, int max_v = -infinity)
		: min_value(min_v), max_value(max_v) {}

	int diff()
	{ return max_value - min_value; }

} tree[2 * size + 100] = {};


void build_tree();
void update(int i, int newval);
MinMax find(int left, int right);


int main()
{
	for(int i = 1, next; i <= size; i++)
	{
		cin >> next;
		tree[i + size - 1] = MinMax(next, next);
	}
	build_tree();

	int queries_n;
	cin >> queries_n;
	for(int first, second; queries_n > 0; queries_n--)
	{
		cin >> first >> second;
                cout << find(first, second).diff() << endl;
	}

	return 0;
}


void build_tree()
{
	for(int i = size - 1; i >= 1; i--)
		tree[i] = MinMax(min(tree[2 * i].min_value, tree[2 * i + 1].min_value),
						 max(tree[2 * i].max_value, tree[2 * i + 1].max_value));
}

void update(int i, int newval)
{
	int v = i + size - 1;
	tree[v] = MinMax(newval, newval);
	v /= 2;
	while(v > 0)
	{
		tree[v] = MinMax(min(tree[2 * v].min_value, tree[2 * v + 1].min_value),
						 max(tree[2 * v].max_value, tree[2 * v + 1].max_value));
		v /= 2;
	}
}

MinMax find(int left, int right)
{
	left += size - 1;
	right += size - 1;
	MinMax result;

	while(left <= right)
	{
		if(left % 2)
		{
			result = MinMax(min(result.min_value, tree[left].min_value),
							max(result.max_value, tree[left].max_value));
			left++;
		}
		if(right % 2 == 0)
		{
			result = MinMax(min(result.min_value, tree[right].min_value),
							max(result.max_value, tree[right].max_value));
			right--;
		}
		left /= 2;
		right /= 2;
	}
	return result;
}
0

@szf, co tu przerabiać skoro samo build_tree ma taką złożoność jak cały algorytm Wibowita?

0

OK. Dostałem wiadomość, że trzeba objaśnić "mój" algorytm (nie jest mój, po prostu miałem to na studiach).

Algorytm w każdym kroku oblicza wartość najlepszego przedziału kończącego się na aktualnie sprawdzanym elemencie. Dla n elementów obliczy więc n przedziałów, wybranie maksa z nich zajmie O(n). Obliczanie najlepszego przedziału kończącego się na k-tym elemencie wiedząc jaki jest najlepszy przedział kończący się na (k-1)-szym elemencie zajmuje O(1). Czemu? Są tylko dwie możliwości: jeżeli (k-1)-szy przedział miał wartość v, a następny element e jest większy od -v, to ich suma jest większa od zera: v + e > v + (-v) = 0, a więc wtedy rozszerzamy przedział (k-1)-szy formując przedział k-ty. W innym wypadku najlepszy przedział kończący się na k-tym elemencie jest pusty (czyli de facto nie kończy się ani nie zaczyna ;) ).

1 użytkowników online, w tym zalogowanych: 0, gości: 1