CareerCup

use this link :en.wikipedia.org/wiki/Maximum_subarray_problem

haha.. the answer should be {40,-10,-10,100,1}
see: ideone.com/mttTG

n1b-algo.blogspot.de/2010/03/largest-sum-of-consecutive-numbers.html

#include<iostream>
using namespace std;
#define N 8

int main(){
int A[]= {-2,-3,-5,40,-10,-10,100,1};
int minI, maxI, max, i, j, temp;
minI= maxI= 0;
max= A[0];

for(i= 0; i< N; i++){
temp= 0;
for(j= i; j< N; j++ ){
temp+= A[j];
if(temp> max){
minI= i;
maxI= j;
max= temp;
}
}
}
cout<<max<<endl;
cout<<"minI "<<minI<<" maxI "<<maxI<<endl;
for(i= minI; i<= maxI; i++)
cout<<A[i]<<" ";
return 0;
}

Result in subset or sub-array?

hrhd

Shouldnt' the answer be {40,100,1}, Please correct me if I am wrong...

scan the array for 1st +ve number and the smallest number
if (no +ve) => return {smallest number}
else

initialize MaxSubset, CurrentSubset ={1st +ve number}
      from next index to last index
            append this number to CurrentSubset
            if (sum(CurrentSubset) >= MaxSubset)
                  MaxSubset = CurrentSubset
            else if (sum(CurrentSubset) <= 0)
                  CurrentSubset = { }
     return MaxSubset

.
you can use indices to track the MaxSubset and CurrentSubset instead of using separate arrays and appending them
. worked in my head, should work when coded ;)

public ArrayList<Integer> longest(int[] data)
{
ArrayList<Integer> result = new ArrayList<Integer>();
ArrayList<Integer> tmp = new ArrayList<Integer>();
int max = 0;
int currentSum = 0;
for(int i = 0; i < data.length; i++)
{
currentSum += data[i];
tmp.add(data[i]);
if(currentSum > max)
{
result.clear(); // reset
result.addAll(tmp); // copy the values
max = currentSum;
}
else if(currentSum < 0)
{
tmp.clear();
currentSum = 0;
}
}
return result;
}

seesharpconcepts.blogspot.in/2012/05/maximum-sum-of-consecutive-numbers-on.html

Similar but complex version of above problem. Approach explained here!

recursion function should be like this:

input[] = {-2,-3,-5,40,-10,-10,100,1}

result[i] = { max{result[i-1]+input[i], input[i]) if i>1
input[i] if i=0;
}


find the max value in result[], that is the answer

shouldn't the subset of the array making the max sum of the above considered array be {40,100,1} ?? i mean is it given in the questions that the subset of the array should contain consecutive elements?

Use maximum subarray problem. Check code at ideone.com/xNf8z

I think this should work...and the runtime is O(n). Explanations are next to the code. Any feedback will be appreciated. :)

import java.util.Vector;

public class MaxArray {
	public static Vector<Integer> calcMax(int[] array) {
		Vector<Integer> temp = new Vector<Integer>();
		int max = 0;
		int sum = 0;
		for (int i = 0; i < array.length; i++) { // if value > 0 -> add to
													// result
			if (array[i] >= 0) {
				sum += array[i];
				max = sum;
				temp.add(array[i]);
			} else { // if value < 0 -> check conditions
				if (i + 1 == array.length) { // if is last index, return without
												// last index
					return temp;
				}
				if (sum + array[i] > 0) { // if previous sum + current negative
											// value > 0 -> add it
					sum += array[i];
					max = sum;
					temp.add(array[i]);
				} else { // else don't add and reset
					max = 0;
					sum = 0;
					temp.clear();
				}
			}
		}
		return temp;
	}

	public static void main(String args[]) {
		int[] arr = { -4, 1, 200, -10, 300, 300, 1, -1 };
		System.out.println(calcMax(arr));
	}
}