최대 2 차원 부분 집합 합

Question

정수의 행렬의 최대 2 차원 하위 ​​집합을 계산하는 알고리즘을 작성하는 작업이 제공됩니다. - 그러나 나는 그런 알고리즘에 대한 도움에 관심이 없으며, 아마도 이것을 해결할 수있는 최악의 경우를 위해 복잡성을 알고 싶어합니다.

현재 알고리즘은 O (n^3)와 같습니다.

필자는 매트릭스를 여러 행렬로 나눔으로써 간단히 행렬 내의 요소를 더하는 것으로 생각해 왔습니다. 따라서 근사해를 찾기 위해 고려해야하는 행렬의 수를 제한합니다.

Answer 1

나는 더 좋은 방법이 없다고 생각했습니다. 적어도 아직 사람에게 알려지지 않았어. 그리고 나는 내가 가진 해결책을 고수 할 것입니다. 그 이유는 간단하기 때문입니다.

Answer 2

최악의 경우 (철저한 검색)는 O (n^3)보다이 분명히 없습니다. 입니다. 웹에 대한 몇 가지 설명이 있습니다.

최상의 경우가 훨씬 좋습니다. O (1). 모든 요소가 음이 아닌 경우, 해답은 행렬 자체입니다. 요소가 양수가 아닌 경우 응답은 0에 가장 가까운 값을 갖는 요소입니다.

마찬가지로 행의 가장자리에 양수가 아닌 정수가 아닌 전체 행/열이있는 경우 검색시이를 제거 할 수 있습니다.