int Max1 (int a[], int n)
{
int s = 0;
int r = 0;
int i = 0;
s = a[0];
r = a[0];
for (i = 1; i < n; ++i)
{
if (s > 0)
{
s += a[i];
}
else
{
s = a[i];
}
if (s > r)
{
r = s;
}
}
return r;
}
The above is for the 1-demension problem, You can apply the similar
algorithm to 2-demension problem.
On Oct 8, 5:41 pm, megha <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I didnt understand...can you tell me more details?
>
> thanks,
>
> On Oct 8, 2:27 am, Jun <[EMAIL PROTECTED]> wrote:
>
>
>
> > You can first solve the 1-dimension similar problem using DP. That's,
> > find the maximum sum of continuous sub sequence of an array. Then you
> > can apply this to 2-dimension problem. That's exactly your problem.
> > The time complexity is O(n^3).
>
> > On Oct 8, 2:04 pm, megha <[EMAIL PROTECTED]> wrote:
>
> > > given N x N matrix of positive and negetive intergers. Write some code
> > > that finds the sub-matrix with teh maximum sum of its elements.
>
> > > Any ideas?
>
> > > Thanks- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
