Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Homework 06 - Dynamic Programming - Moving Window
- *
- * Problem 1: Max Consecutive Sum
- *
- * Prompt: Given an array of integers find the sum of consecutive
- * values in the array that produces the maximum value.
- *
- * Input: Unsorted array of positive and negative integers
- * Output: Integer (max consecutive sum)
- *
- * Example: input = [6, -1, 3, 5, -10]
- * output = 13 (6 + -1 + 3 + 5 = 13)
- *
- */
- import java.io.*;
- import java.util.*;
- class Problems {
- // Time Complexity:
- // Auxiliary Space Complexity:
- public static void main(String[] args){
- int[] arr ={-6, -1, 3, -5, 10};
- System.out.println(maxConsecutiveSum(arr));
- }
- public static int maxConsecutiveSum(int[] arr) {
- int len = arr.length;
- if(len == 0){
- return 0;
- }
- if(len == 1){
- return arr[0];
- }
- if(len == 2){
- if(arr[0] > 0 && arr[1] > 0){
- return arr[0] + arr[1];
- }else{
- return Math.max(arr[0],arr[1]);
- }
- }
- //instantiate current maxSum to the value of initial element in the arr
- int maxSum = Integer.MIN_VALUE;
- //sum var keeps running total and then will be compared to max
- int sum = Math.max(arr[0],0);
- for (int i = 1; i < len; i++){
- //if the max sum + next int is less than that int alone, max = next int
- sum = Math.max(0, sum + arr[i]);
- maxSum = Math.max(maxSum, sum);
- }
- return maxSum;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement