A nxm matrix consists of positive and negative numbers. How to find any region which is connected (i.e., two entries are either side-by-side or up-and-down, not diagonal) that has the largest sum? Is this problem NP-hard? Then, from which NP-complete problem is this reduced?
2006-09-11 10:18:31 · 2 answers · asked by arnab.bhattacharya 1 in Science & Mathematics ➔ Mathematics
Not non-polynomial because your matrix is finite. There will always be a finite process that exhausts all possibilities
How many paths in an nxm matrix?
Start with nxn it's easier and can generalize later.
Just sum all paths rejecting those with negative numbers
2006-09-11 11:50:27 · answer #1 · answered by bubsir 4 · 0⤊ 0⤋
Interesting problem... seems like an NP problem to me. Since the known NP-complete problems can be shown to be equivalent, your last answer can be: any.
I will think about a nice algorithm yet.
2006-09-11 17:57:57 · answer #2 · answered by dutch_prof 4 · 0⤊ 0⤋