Pomoc z dwoma algorytmami

Witam,
Jestem początkującym programistą c++.
Mam do rozwiązania 2 zadania i szczerze myślę już jakiś czas nad jakimś ciekawym algorytmem ale nic nie przychodzi mi do głowy jak je rozwiązać. A mianowicie oto one.

Pierwsze zadanie polega na tym że najpierw wczytuje n liczb i mam je podzielić na 2 (dodać do 2 zmiennych) tak aby na koniec różnica pomiędzy tymi zmiennymi była jak najmniejsza.
Dla przykładu
Mamy 2 2 2 5
Wynik to 6 i 5

Lub
Mamy
5 5 5 10 10
Wynik to 20 i 15

Drugie zadanie polega na tym że wczytujemy tablicę prostokątną dwuwymiarową liczb dodatnich oraz zmienną oznaczającą bok kwadratu.
Mamy znaleźć maksymalny kwadrat o podanym boku w tej tablicy(czyli taki kwadrat który po zsumowaniu elementów tablicy które obejmuje daje największą wartość).
W wyniku podajemy tą wartość

Dla przykładu
http://scr.hu/2kgz/7dp0f

Z góry dziękuję za wszelką pomoc.

Do pierwszego zadania wymyśliłem takie coś że tworze tablice tych n liczb, sortuje ją malejąco a następnie dodaje od początku kolejnie liczby do zmiennej która jest w danym momencie mniejsza.
Wrzuciłem na platformę i mam 78/100
wiersz 1: wczytano '18348', a oczekiwano '18346'
6 wiersz 1: wczytano '201597', a oczekiwano '201596'

Do drugiego zadania dalej nie mam pomysłu

W drugim wystarczy sprawdzić wszystkie kombinacje:)

Raczej interesuje mnie bardziej optymalne rozwiązanie :)

I tak i tak musisz sprawdzić wszystkie możliwości jak zapamiętasz po przednie wyniki to nie będzie tak źle ;)
Skąd masz te zadania ze możesz sprawdzać wyniki?

Z koła informatycznego w mojej szkole są te zadania i to jest ich osobista platforma. Dalej proszę wszystkich o pomoc bo jestem pewien że sprawdzenie wszystkich możliwości to nie jest poprawne rozwiązanie

W pierwszym w każdym kroku musisz wybierać liczbę powodującą najmniejszą różnice najbliższą zera, w kolejnym problem redukuje się do tego samego z wartościami mniejszymi i o wartość różnicy(a przynajmniej tak mi się wydaje:P) i zjedna zmienną mniej, powtarzasz do skutku.

Pierwsze zadanie polega na tym że najpierw wczytuje n liczb i mam je podzielić na 2 (dodać do 2 zmiennych) tak aby na koniec różnica pomiędzy tymi zmiennymi była jak najmniejsza.
Dla przykładu
Mamy 2 2 2 5
Wynik to 6 i 5

A ten algorytm to ma działać w czasie wielomianowym (np. O(n^100))? ;)
Bo jeśli nie musi, to proste rozwiązanie - sprawdzenie wszystkich możliwości.
Dla każdego elementu w tablicy rozważasz dwie opcje: "element trafia do pierwszej tablicy" oraz "element trafia do drugiej tablicy", a po przyporządkowaniu liczysz różnicę sum.
Złożoność: O(2^n)

A jeśli musi być wielomianowo to powodzenia. Twoje zadanie to klasyczny problem NP-zupełny:
https://en.wikipedia.org/wiki/Partition_problem

There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.

Są dobre przybliżenia (ale to Ci raczej nie pomoże) oraz algorytmy uzależniające czas wykonania np. od sumy elementów w tablicy, albo algorytmy działające dobrze w praktyce, poszukaj za tym problemem po nazwie, jest sporo tego w sieci.

Drugie zadanie polega na tym że wczytujemy tablicę prostokątną dwuwymiarową liczb dodatnich oraz zmienną oznaczającą bok kwadratu.
Mamy znaleźć maksymalny kwadrat o podanym boku w tej tablicy(czyli taki kwadrat który po zsumowaniu elementów tablicy które obejmuje daje największą wartość).
W wyniku podajemy tą wartość

W drugim wystarczy sprawdzić wszystkie kombinacje:)

I tak i tak musisz sprawdzić wszystkie możliwości jak zapamiętasz po przednie wyniki to nie będzie tak źle ;)

Trochę słabe algorytmicznie rozwiązanie :P.

A odnośnie lepszego: najpierw musisz obliczyć sumę pól dla wszystkich prostokątów z jednym wierzchołkiem w lewym górnym rogu - można to zrobić w czasie O(n).

Czyli z tablicy A:

1 1 1
1 1 1
1 1 1

Otrzymujesz tablicę sum S:

1 2 3
2 4 6
3 6 9

(każde pole to suma elementów powyżej i z lewej strony)

A później możesz obliczyć pole każdego prostokąta w czasie O(1) ((x1+1, y1+1), (x2, y2)) jako S(x2, y2) - S(x2, y1) - S(x1, y2) + S(x1, y1) (rozrysuj sobie)

A kiedy możesz obliczyć pole każdego prostokąta (czyli tez kwadratu) w czasie O(1) to wtedy dopiero można wykonać pętlę po wszystkich możliwościach, w czasie O(n)

@korec123 twoje rozwiazanie dla 1) to jest klasyczne rozwiązanie zachłanne dla tego problemu. Kontrprzykład dla niego to np.
8,7,6,5,4 -> twój algorytm podzieli to na {8,6} i {7,5,4} z różnicą 2 podczas gdy można {8,7} i {4,5,6} z różnicą 0

Dla drugiego problemu najlepiej zrobić to dynamicznie, tworząc najpierw tablicę sum. Zauważ że znając sumę w kwadracie który zaczyna się w (0,0) możesz łatwo policzyc sumę kwadratu zaczynającego się w (0,1) bo wystarczy od tej poprzedniej sumy odjąć sumę z pierwszej kolumny i dodać sumę z kolumny k+1 (gdzie k to bok kwadratu).
Żeby się szybciej liczyło możesz wyliczyc sobie częściowe k-elementowe sumy dla wszystkich kolumn oraz wierszy (czyli sumy k kolejnych elementów w kolumnie i w wierszu), to wymaga dwóch przejść przez tablicę więc 2nm więc w sumie będzie 3nm -> O(nm) gdzie n,m to wymiary wejściowej tablicy

Zadanie 2 rozwaliłem w 26 linijkach za pomocą sum prefiksowych. Najpierw stworzyłem pomocniczą tablicę gdzie element tab[i][k] oznacza sumę pól od [0][0] do tego elementu. Potem prosto odejmuje sobie punkty, weszło na 100.

Dalej jednak mam kłopot z zadaniem 1. Jak widać już jest kontrargument do mojego rozwiązania i nie wiem jak zrobić to inaczej. Nie do końca rozumiem też rozwiązanie MSM jakby ktoś mógł spróbować ocenić czy jest poprawne i mi je potem wytłumaczyć byłbym wdzięczny.

Zadanie 2 rozwaliłem w 26 linijkach za pomocą sum prefiksowych. Najpierw stworzyłem pomocniczą tablicę gdzie element tab[i][k] oznacza sumę pól od [0][0] do tego elementu. Potem prosto odejmuje sobie punkty, weszło na 100.

Tak jakby co, to słowo w słowo to co opisałem (nie wiem czy wiesz, ale chciałem zaznaczyć).

Dalej jednak mam kłopot z zadaniem 1. Jak widać już jest kontrargument do mojego rozwiązania i nie wiem jak zrobić to inaczej. Nie do końca rozumiem też rozwiązanie MSM jakby ktoś mógł spróbować ocenić czy jest poprawne i mi je potem wytłumaczyć byłbym wdzięczny.

Ja napisałęm najbardziej naiwne rozwiązanie (zupełny bruteforce), da się lepiej.
Zauważyłem tylko że to problem NP zupełny, więc nie jest znany żadny szybki algorytm rozwiązujący ten problem. Podałem też link do wikipedii oraz hasło za którym możesz szukać (mogę tu przekleić zawartość wikipedii i/lub artykułów z sieci, ale chyba nie ma sensu).

http://scr.hu/2kgz/if5uk
Oto pełna treść zadania, mam nadzieję że to pomoże.
Szukam rozwiązania dynamicznego bo w sumie na tym miały opierać się te zadania według autora.