CareerCup

@Oshin,
The question what I posted is exactly what he asked me.

For Example: If we have { 5 6 7 3 4 5 6 3} list of 8 int numbers we have and

sum of first 3 adjacent numbers (5 +6 +7) =18
sum of next 3 adjacent numbers (6+7+3) =16
sum of next (7+3+4) = 14

like wise we need to find out maximum sum of all these ......Please let me know if you are still not clear......

So if the m is given instead of a constant number 3, we just remember the previous sum instead of summing up in every loop.


int maxSum = 0, currentSum = 0, size = a.length;
for (int i = 0; i <= (size - m); i++) {
if (i < m - 1) {
currentSum += a[i];
}
else if (i = m - 1) {
maxSum = currentSum;
}
else if (i > m - 1) {
currentSum = currentSum + a[i] - a[i - m];
if (currentSum > maxSum) {
maxSum = currentSum;
}
}
}

return maxSum;

<pre lang="java" line="1" title="CodeMonkey21769" class="run-this">/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package subseq;


public class Main {


public static void main(String[] args) {
int a[] = {1,2,3,4,5,6,7,8};
int bigSum = 0,sum=0,index =0;
for(int i=0;i<a.length-2;i++)
{
int j = i;
sum=a[j]+a[j++]+a[j++];
if(sum>bigSum)
{
bigSum = sum;
index = i;
}
else
{

}
}
System.out.println("sum : "+bigSum+ " index: "+index);
}


}
</pre><pre title="CodeMonkey21769" input="yes">
</pre>

possible in O(N), any one knows better than this?

Without touching all no. finding MAX sum is not possible....! so O(n)is the best sol... i think...! :)

Guys..in the above code..ppl forgot to consider if the loop has -ve numbers in last 3 digits like {5,6,7,2,-1,0,19)...since we run the length-2..there can be a scenario where we can miss the last element.

Sort the list in descending order and then pick first m characters.

public static int getMax(int[] array, int m) {
		int maxsum=0,oldsum,currsum=0;
		for(int i=0;i<m;i++) maxsum+=array[i];
		oldsum=maxsum;
		for(int i=1;i<=(array.length-m);i++) {
			currsum = oldsum-array[i-1]+array[i+m-1];
			if(currsum>maxsum) {
				maxsum = currsum;
			}
			oldsum = currsum;
		}
		return maxsum;
	}

The question does not ask for the max sum.. it asks for the tuple that makes the max sum !!



package testPrograms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class MaxSumTuple
{
private int[] tuple;

public MaxSumTuple()
{
tuple = new int[3];
}
public int[] findTuple(List<Integer> listInt)
{
int sumOld = 0,sumNew = 0;
if (listInt.size() <= 3)
{
for (int i = 0; i < listInt.size(); i++)
{
this.tuple[i] = listInt.get(i);
return tuple.clone();
}
}

for(int i=0;i<listInt.size() - 2;i++)
{
sumNew = listInt.get(i) + listInt.get(i+1) + listInt.get(i+2);
if(sumNew > sumOld)
{
sumOld = sumNew;
updateTuple(i,listInt);
}

}

return tuple.clone();

}

public void updateTuple(int index,List<Integer> list)
{
for(int i=0;i<tuple.length;i++)
{
tuple[i] = list.get(index + i);
}
}
public static void main(String []args)
{
List<Integer> list = new ArrayList<Integer>();
Random random = new Random();
for(int i=0;i<10;i++)
{
list.add(random.nextInt(100));
}

MaxSumTuple maxSumTuple = new MaxSumTuple();
int []tuple = maxSumTuple.findTuple(list);
System.out.println(list);
System.out.println(Arrays.toString(tuple));




}

}

whattt...I am sure I get the question wrongly OR was he looking for a better solution than O(n) :O

better than O(n)?

Try this i think it will work..



int maxsum=0,thissum=0;
for(int i=0;i<(size-2);i++)
{

thissum=a[i]+a[i+1]+a[i+2];
if(thissum<0) thissum=0;
if(maxsum<thissum) maxsum=thissum;
}

if m is given instead of 3 , how will we solve this