Advertisement
gelita

Max Consecutive Sum dynamic program java

Feb 14th, 2020
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.51 KB | None | 0 0
  1. /*
  2.  *  Homework 06 - Dynamic Programming - Moving Window
  3.  *
  4.  *  Problem 1: Max Consecutive Sum
  5.  *
  6.  *  Prompt:    Given an array of integers find the sum of consecutive
  7.  *             values in the array that produces the maximum value.
  8.  *
  9.  *  Input:     Unsorted array of positive and negative integers
  10.  *  Output:    Integer (max consecutive sum)
  11.  *
  12.  *  Example:   input = [6, -1, 3, 5, -10]
  13.  *             output = 13 (6 + -1 + 3 + 5 = 13)
  14.  *
  15.  */
  16.  
  17.  import java.io.*;
  18.  import java.util.*;
  19.  
  20.  class Problems {
  21.  
  22.    // Time Complexity:
  23.    // Auxiliary Space Complexity:
  24.    public static void main(String[] args){
  25.      int[] arr ={-6, -1, 3, -5, 10};
  26.      System.out.println(maxConsecutiveSum(arr));
  27.    }
  28.    
  29.    public static int maxConsecutiveSum(int[] arr) {
  30.      int len = arr.length;
  31.      if(len == 0){
  32.        return 0;
  33.      }
  34.      if(len == 1){
  35.        return arr[0];
  36.      }
  37.      if(len == 2){
  38.        if(arr[0] > 0 && arr[1] > 0){
  39.         return arr[0] + arr[1];
  40.        }else{
  41.          return Math.max(arr[0],arr[1]);
  42.        }
  43.      }  
  44.      //instantiate current maxSum to the value of initial element in the arr
  45.      int maxSum = Integer.MIN_VALUE;
  46.      //sum var keeps running total and then will be compared to max
  47.      int sum = Math.max(arr[0],0);
  48.      for (int i = 1; i < len; i++){
  49.       //if the max sum + next int is less than that int alone, max = next int
  50.         sum = Math.max(0, sum + arr[i]);
  51.         maxSum = Math.max(maxSum, sum);
  52.     }
  53.     return maxSum;
  54.     }
  55.    }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement