największa suma algorytm?

Odpowiedz Nowy wątek
2011-08-07 23:48
SUMA
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?

Pozostało 580 znaków

2011-08-08 00:46
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

Pozostało 580 znaków

2011-08-08 01:29
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); 
}

"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2011-08-08 01:38
Algorytm nie przechodzi wszystkich testów i czas wykonania jest hoho :/ - Lubie cycki :) 2011-08-08 18:50
Który algorytm i jakich testów? - Wibowit 2011-08-08 19:07

Pozostało 580 znaków

2011-08-08 01:34
bo
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.

nie sprawdzi się - byku_guzio 2011-08-08 01:43

Pozostało 580 znaków

2011-08-08 01:37
ofidyfil
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.

Pozostało 580 znaków

2011-08-08 01:39
ofidyfil
0

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

Pozostało 580 znaków

2011-08-08 01:40
0

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


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-08-08 01:41
ofidyfil
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.

Pozostało 580 znaków

2011-08-08 01:54
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);
        }
    }
}

"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-08-08 02:24
ofidyfil
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?

Pozostało 580 znaków

2011-08-08 02:25
ofidyfil
0

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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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