Max Array Sum

  • + 0 comments

    Space complexity O(1) and time complexity O(n) Many answers here have space complexity O(n)

    public static int maxSubsetSum(List<Integer> arr) {
        int valueMinus1 = 0;
        int valueMinus2 = 0;
        int sum = 0;
        for (int i = 0; i < arr.size(); i += 1) {
            if (arr.get(i) <= 0) {
                valueMinus1 = valueMinus2 = Math.max(valueMinus1, valueMinus2);
            } else {
                sum = Math.max(valueMinus1, arr.get(i) + valueMinus2);
                valueMinus2 = valueMinus1;
                valueMinus1 = sum;
            }
        }
        return sum;
    }