Application Development, Product to Market
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Maximum Sum of Continuous Subarray

11/20/2013

0 Comments

 
Given an array with integers, find the largest sum of continuous subarray. This maximum subarray problem was first posed in 1977. Jay Kadane solved it in linear time (O(n)) in 1988.

The Approach

The brute-force way of solving this is to use 2 for-each loops, one inside another, to loop through all combination. However, the linear approach is to use dynamic programming to break down the problem into small ones.

Characteristics of dynamic programming:
  1. Optimal substructure - The solution to a problem in a bigger set can be efficiently represented in terms of a solution to a problem in an incrementally smaller set. That is, problem can be divided into stages.
  2. Recursive nature of the solution.
  3. Bottom-Up (solve smaller problems first)

Thought Process

The bigger problem is to find all the combination of contiguous subarrays of a given array A. Among all the combination of contiguous subarrays, find the maximum sum. A smaller problem is to find the maximum sum of contiguous subarray of a given smaller array.

When you add an element to a smaller array, "the max of possible sub sequence sum of the bigger array that includes the last element as part of the sum" is either the added element itself, or "the previous max of possible sub sequence sum of the bigger array that includes the previous added element as part of the sum" plus the newly added element. The recursive nature of the solution is:
m(i) = the max of possible sub sequence sum of the array that includes the last element as part of the sum
      = max{m(i-1)+A[i], A[i]}
For example, let's say A = {-9,-8,17,1,-1,0,1}
m(1) = -9
m(2) = max(-9-8, -8) = -8
m(3) = max(-8+17, 17) = 17
m(4) = max(17+1, 1) = 18
m(5) = max(18-1, -1) = 17
m(6) = max(17+0, 0) = 17
m(7) = max(17+1, 1) = 18
The answer is the max of all possible m(i).
max(m(i)) = 18

Code Sinppet

class Test{
  public static int maxSubarraySum(int[] A){
    int m = -99999;
    int max_subarray_sum = m;
    for(int i=0; i<A.length; ++i){
      m = Math.max(m + A[i], A[i]);
      max_subarray_sum = Math.max(max_subarray_sum, m);
    }
    return max_subarray_sum;
  }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] input1 = {2,3,-1};
    int[] input2 = {-9,-8,17,1,-1,0,1};
    int[] input3 = {0,-1,1,1,-1,0,1};
 
    System.out.println(maxSubarraySum(input1)); // print 5
    System.out.println(maxSubarraySum(input2)); // print 18
    System.out.println(maxSubarraySum(input3)); // print 2
  }
}

References

How can I effectively practice Dynamic Programming to improve my skills?
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos used under Creative Commons from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar