wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Finding subarray with max. sum
        
(Message started by: mcprabhakaran on May 16^th, 2007, 4:13am)

Title: Finding subarray with max. sum
Post by mcprabhakaran on May 16^th, 2007, 4:13am

Hello Friends,

Tell me some ideas to find a sub array with max.total and min.length in the given array which has positive and negative numbers.

Ex. a[]={1,2,-1,-2,0}

sub array={1,2} length=2

Title: Re: Finding subarray with max. sum
Post by towr on May 16^th, 2007, 6:24am

Take the first positive element, note it's position.
Save the current maximum and the range.
Add the next item, if the total is greater than the current maximum, update the current maximum and the range. If it is less or equal to zero, clear the old starting position and progress to the next positive element and repeat.

Something alogn those lines.

Title: Re: Finding subarray with max. sum
Post by SMQ on May 16^th, 2007, 6:59am

int sum = a[0], start = 0, length = 1;
int bestSum = sum, bestStart = start, bestLength = length;

for(int i = 1; i < a.length; i++) {
if (sum < 0) { sum = 0; start = i; length = 0; }
sum += a[i]; length++;
if (sum > bestSum || sum == bestSum && length < bestLength) {
bestSum = sum;
bestStart = start;
bestLength = length;
}
}

--SMQ

Title: Re: Finding subarray with max. sum
Post by mcprabhakaran on May 17^th, 2007, 4:55am

Fine .. Thanks .. For ur code... :) :) :)

Title: Re: Finding subarray with max. sum
Post by anshulk_scorp on Jun 28^th, 2007, 9:37pm

Well...Dynamic programming helps at places...
If A(i) is ith element of array and. S(i) is sum of largest subarray which has i as its tail element:

S(0)=A(0)
S(i)=MAX( S(i-1)+A(i) , A(i) )

I have used round brackets.....but this can be done with memoization

Title: Re: Finding subarray with max. sum
Post by findmeeifucan on Jul 12^th, 2007, 7:35pm

This is java code to solve this problem

import java.util.Vector;

public class SubArray_MaxSum {

/** Creates a new instance of SubArray_MaxSum */

public static void main(String args[]){
new SubArray_MaxSum().start();
}

public void start(){
int arr[] = {-3,-3,3,-3,5};
Findmaxsubarray(arr);
}

public void Findmaxsubarray(int[] arr){
Range x, max;
x = new Range(0);
max = new Range(0);
for(int i=0;i<arr.length;i++){
if(x.sum <= 0){
x.init(i);
}
x.increaseRight(arr[i]);
if(x.sum>max.sum)
max = new Range(x);
}
System.out.println(""+max.left+" "+max.right+" "+max.sum);
}
}

class Range{
public int left;
public int right;
public int sum;

public Range(int l){
init(l);
}

public Range(Range r){
init(0);
left =r.left;
right=r.right;
sum=r.sum;
}
public void init(int l){
left =l;
right=l-1;
sum=0;
}

public void increaseRight(int val){
right++;
sum+=val;
}
};