Friday, November 25, 2011

Find largest subset sum for a given array

Problem: Given an array of N integers (both positive and negative), find the sub-sequence with largest sum.

For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest sum is 10 (start index = 4, end index = 7)
Posted by at

1 comment:

  1. AbhiNovember 25, 2011 at 2:11 PM

    public class LargestSubsetSum {

    private int startIndex;
    private int endIndex;
    private int maxSubSetSum;

    public void findLargestSubSetSum(int[] inputArr) {
    startIndex = 0;
    endIndex = 0;
    maxSubSetSum = inputArr[0];
    int i = 1;
    int sum = 0;
    int candidateStartIndex = 1;
    while (i < inputArr.length) {
    sum += inputArr[i];
    if (sum > maxSubSetSum) {
    startIndex = candidateStartIndex;
    endIndex = i;
    maxSubSetSum = sum;
    }
    if(sum < 0){
    sum = 0;
    candidateStartIndex = i+1;
    }
    i++;
    }
    }

    public void printResult() {
    System.out.println("Max subset sum : " + maxSubSetSum);
    System.out.println("Start index : " + startIndex);
    System.out.println("End Index : " + endIndex);
    }
    public static void main(String[] args) {
    LargestSubsetSum largestSubsetSum = new LargestSubsetSum();
    int[] inputArr = { 1, 2, -5, 4, 5, -1, 2, -11 };
    largestSubsetSum.findLargestSum(inputArr);
    largestSubsetSum.printResult();
    }
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)