hi all,
Given an array containing both positive and negative integers, we r
required to find the sub-array with the largest sum
i have the solution to his problem which theoritically is O(n^2) but
practically is much faster as it uses Dynamic Programming Logic.
It works as filling the upper half of the N*N matrix where a cell
[i][j] represent the sum of the elements from ith to the jth index in
the original given array (A) i.e a[i][j] = A[i] + A[i+1] + ... + A[j];
now we just find the max. element in the A array and give its
coordinates as our answer.
My code is as follows:
// initialize the 2D arrays diagonal by the elements of the original
// array A
for(int i=0, j=0;i<n;i++.j++)
a[i][j] = A[i];
// initialize the max till now and the coordinates of the max element
max = a[n-1][n-1];
x=n-1; y=n-1;
for(i=n-1;i>=0;i--)
for(int j==i+1;j<n;j++)
{
a[i][j] = a[i+1][j] + A[i];
// update max, if required
if(a[i][j] > max)
{
max = a[i][j];
x=i; y=j;
}
}
Can nyone help me finding its O(n) solution?and ny flaw in my concept ?
