UVa 108 is rated as a Level 1 (easy) problem by uHunt, but its solution nevertheless contains some interesting techniques. Here’s a summary of the problem statement:
Given an $N \times N$ array $A$ of positive and negative integers, print the sum of the nonempty subarray of $A$ that has the maximum sum. The sum of a subarray is defined as the sum of its elements.
uHunt lists this problem in the section called Max 2D Range Sum, a subcategory of Dynamic Programming. But before we get into the dynamic programming solution, let’s examine the Complete Search approach.