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?

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