Author |
Topic: Finding subarray with max. sum (Read 802 times) |
|
mcprabhakaran
Junior Member
Posts: 62
|
 |
Finding subarray with max. sum
« on: May 16th, 2007, 4:13am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding subarray with max. sum
« Reply #1 on: May 16th, 2007, 6:24am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Finding subarray with max. sum
« Reply #2 on: May 16th, 2007, 6:59am » |
Quote Modify
|
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
|
| « Last Edit: May 17th, 2007, 5:37am by SMQ » |
IP Logged |
--SMQ
|
|
|
mcprabhakaran
Junior Member
Posts: 62
|
|
Re: Finding subarray with max. sum
« Reply #3 on: May 17th, 2007, 4:55am » |
Quote Modify
|
Fine .. Thanks .. For ur code... 
|
|
IP Logged |
|
|
|
anshulk_scorp
Newbie
Posts: 8
|
|
Re: Finding subarray with max. sum
« Reply #4 on: Jun 28th, 2007, 9:37pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
findmeeifucan
Newbie
Gender:
Posts: 2
|
|
Re: Finding subarray with max. sum
« Reply #5 on: Jul 12th, 2007, 7:35pm » |
Quote Modify
|
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;
}
};
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print