Max Array Sum

  • + 0 comments

    Solution for Java

    public static int maxSubsetSum(List<Integer> arr) {
                int[] dp = new int[arr.size()];
                // First init value of dp[0] and dp[1], if negative then set to 0
                dp[0] = Math.max(arr.get(0), 0);
                dp[1] = Math.max(dp[0], arr.get(1));
    
                for (int i = 2; i < dp.length; i++) {
                    // If value of dp[i - 2] + arr.get(i) > dp[i - 1] then dp[i] = dp[i - 2] + arr.get(i) else dp[i] = dp[i - 1
                    dp[i] = Math.max(dp[i - 2] + arr.get(i), dp[i - 1]);
                }
    
                return dp[dp.length - 1];
            }        }