Showing posts with label Kadane Max Sum. Show all posts
Showing posts with label Kadane Max Sum. Show all posts

Codility 7.1 Max Double Slice Sum | codesolutiony


Codility 7.1 Max Double Slice Sum | codesolutiony
A non-empty zero-indexed array A consisting of N integers is given. A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + … + A[Y − 1] + A[Y + 1] + A[Y + 2] + … + A[Z − 1].
For example, array A such that:
    A[0] = 3      A[1] = 2      A[2] = 6      A[3] = -1      A[4] = 4      A[5] = 5      A[6] = -1      A[7] = 2
contains the following example double slices:
  • double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
  • double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
  • double slice (3, 4, 5), sum is 0.
The goal is to find the maximal sum of any double slice.

X.  http://liweithu.me/maximum_slice_problem/
乍一看这个要比最大子段和高级，似乎要枚举最大字串的右边界i和中间点center，但其实只用枚举右边界i，右边界从i-1变成i之后，中间点只可能是center或者i-1中的一个，中间点为k的时候左边界不变最优，中间点为i-1的时候需要求最优左边界（这就是个内嵌的MaxSliceSum问题）；还有一种情况就是只保留A[i-1]一个元素。整体复杂度仍然是时间 O(N),空间 O(1)
int solution(vector<int> &A) {
    if(A.size() <= 3) return 0;
    int max_left = 0;//中间点为i-1右边界为i时左段最大值
    int max_ending = 0;//右边界为i时两段最大值
    int center = 1;//中间点
    int max_slice = 0;
    for(int i = 3; i< A.size(); i++){
        max_left = max(max_left+A[i-2], A[i-2]);//MaxSliceSum问题
        max_ending = max(max_ending+A[i-1], A[i-1], max_left);//MaxDoubleSliceSum问题
        if(max_ending == A[i-1]) center = i-2;
        else if(max_ending == max_left) center = i-1;
        if(max_ending > max_slice) max_slice = max_ending;
    }
    return max_slice;
}

X.  http://blog.csdn.net/caopengcs/article/details/17491395
还有一种思路就是只枚举中间点k，分别算以k-1结尾和k+1开头的最大字段和，然后再把两者拼起来
  1. int solution(vector<int> &A) {  
  2.     int n = A.size(), temp = 0;  
  3.     vector<int> b;  
  4.     b.resize(n);  
  5.     for (int i = 1; i < n; ++i) {  
  6.         if (temp < 0) {  
  7.             temp = 0;  
  8.         }  
  9.         b[i] = temp;  
  10.         temp += A[i];  
  11.          
  12.     }  
  13.     temp = 0;  
  14.     int result = 0;  
  15.     for (int i = n - 2; i ; --i) {  
  16.         if (temp < 0) {  
  17.             temp = 0;  
  18.         }  
  19.         result = max(result, temp + b[i]);  
  20.         temp += A[i];  
  21.     }  
  22.     return result;  
  23.           
  24.           
  25. }
X.
    public int solution(int[] A) {
        int[] fromLeft = new int[A.length];
        int[] fromRight = new int[A.length];
        int max = 0;
        for (int i = 2; i < A.length; i++) {
            fromLeft[i] = Math.max(0, fromLeft[i-1] + A[i-1]);
        }
        for (int i = A.length - 3; i >= 0; i--) {
            fromRight[i] = Math.max(0, fromRight[i+1] + A[i+1]);
        }
        for (int i = 1; i < A.length - 1; i++) {
            max = Math.max(max, fromLeft[i] + fromRight[i]);
        }
        return max;
    }

http://www.cnblogs.com/easonliu/p/4453314.html
 7 int solution(vector<int> &A) {
 8     // write your code in C++11
 9     if (A.size() <= 3) return 0;
10     vector<int> left(A), right(A);
11     int n = A.size();
12     left[0] = left[n-1] = 0;
13     right[0] = right[n-1] = 0;
14     for (int i = 1; i < n - 1; ++i) {
15         left[i] = max(left[i], left[i] + left[i-1]);
16         right[n-1-i] = max(right[n-1-i], right[n-1-i] + right[n-i]);
17     }
18     int res = 0;
19     for (int i = 1; i < n - 1; ++i) {
20         res = max(res, left[i] + right[i] - 2 * A[i]);
21     }
22     return res;
23 }
https://github.com/acprimer/Codility/blob/master/src/Lesson7/MaxDoubleSliceSum.java

// dp from two directions public int solution(int[] A) {
int n = A.length;
int[] dpL = new int[n];
int[] dpR = new int[n];
for (int i = 1; i < n - 1; i++) {
dpL[i] = Math.max(dpL[i - 1] + A[i], 0);
}
for (int i = n - 2; i > 0; i--) {
dpR[i] = Math.max(dpR[i + 1] + A[i], 0);
}
int ans = 0;
for (int i = 1; i < n - 1; i++) {
ans = Math.max(ans, dpL[i - 1] + dpR[i + 1]);
}
return ans;
}

http://stackoverflow.com/questions/28631437/max-double-slice-sum-codility-o1-space-complexity-fail-performance-test-case
    public int solution(int[] A) {      
        long maxDS = 0;
        long maxDSE = 0;
        long maxS = A[1];

        for(int i=2; i<A.length-1; ++i){                        
            maxDSE = Math.max(maxDSE+A[i], maxS);       
            maxDS = Math.max(maxDS, maxDSE);                                    
            maxS = Math.max(0, Math.max(A[i], maxS + A[i]));     
        }

        return (int)maxDS;
    }
Read full article from Codility 7.1 Max Double Slice Sum | codesolutiony
at
Labels: , ,

Codility ‘MaxSliceSum’ Solution | MartinKysel.com


Codility 'MaxSliceSum' Solution | MartinKysel.com
Find a maximum sum of a compact subsequence of array elements.
http://rafal.io/posts/codility-max-slice-sum.html
public int solution(int[] A) {
    int maxEndingHere = A[0];
    int maxSoFar = A[0];
    for(int i = 1; i < A.length; i++){
        maxEndingHere = Math.max(A[i], maxEndingHere + A[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}
Read full article from Codility 'MaxSliceSum' Solution | MartinKysel.com
at
Labels: ,

Subsequences in an array with maximum difference - PrismoSkills


Subsequences in an array with maximum difference - PrismoSkills
Problem: Find two contiguous subsequences in an array with maximum difference.
The subsequences may be overlapping.

Solution: This is an extended case of Kadane's algorithm.
Here we find max-subsequence using Kadane and then the min-subsequence using Kadane.
Desired result is the difference of sums of these two subsequeces.
Read full article from Subsequences in an array with maximum difference - PrismoSkills
at
Labels: ,

Find Max sum in a 2D array | PROGRAMMING INTERVIEWS


Find Max sum in a 2D array | PROGRAMMING INTERVIEWS

We can extend this 1D kadane algorithm to 2D kadane algorithm and can find the max sum in a N*N matrix in O(N^3).

 What is needed for extending kadane algorithm is as followed:
  1. Traverse matrix at row level.
  2. have a temporary 1-D array and initialize all members as 0.
  3. For each row do following:
    •   add value in temporary array for all rows below current row (including current row)
    •   apply 1-D kadane on temporary array
    •   if your current result is greater than current maximum sum, update.
We are actually finding maximum sum sub-matrix by adding continuous rows in the original matrix and finding maximum value indexes for left and right columns.

 In this algorithm we calculate the prefix sum for all possible row combination in O(n2) and then take out their maximum contigous sum in O(n) time. Thus doing the task in O(n3) time. 
http://www.shuatiblog.com/blog/2014/08/01/Max-Sum-In-2D-Array/
  1. Traverse matrix at row level.
  2. have a temporary 1-D array and initialize all members as 0.
  3. For each row do following
    1. add value in temporary array for all rows below current row
    2. apply 1-D kadane on temporary array
    3. if your current result is greater than current maximum sum, update.
public int maxSum(int[][] A) {
    int m = A.length;
    int n = A[0].length;
    int maxResult = Integer.MIN_VALUE;
    for (int i = 0; i < m; i++) {
        int[] temp = new int[n];
        for (int j = i; j < m; j++) {
            // from row#i to row#(m-1), add the number into temp[]
            for (int k = 0; k < n; k++) {
                temp[k] += A[j][k];
            }
            // find max sum for 1D array
            maxResult = Math.max(maxResult, maxSum(temp));
        }
    }
    return maxResult;
}

private int maxSum(int[] B) {
    int sumSoFar = 0;
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < B.length; i++) {
        maxSum = Math.max(maxSum, sumSoFar + B[i]);
        sumSoFar = Math.max(0, sumSoFar + B[i]);
    }
    return maxSum;
}
http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_07_-_Submatrix_with_largest_sum.jsp
from column level:
 


Basically, kadane's algorithm (complexity: O(n)) is used inside a naive maximum sum sub-array problem (complexity: O(n2)).
This gives a total complexity of O(n3)
public static double max1DSubarray(double[] array, MutableInt returnStart, MutableInt returnEnd)
{
double max_so_far = 0;
double max_ending_here = 0;

int currentStart = 0;
for (int i = 0; i < array.length; i++)
{
max_ending_here = max_ending_here + array[i];
if (max_ending_here > 0)
{
if (max_ending_here > max_so_far)
{
max_so_far = max_ending_here;
returnStart.setValue(currentStart);
returnEnd.setValue(i);
}
}
else
{
currentStart = i + 1;
max_ending_here = 0;
}
}
return max_so_far;
}
int findMaxSum (int matrix[numRows][numCols])
{
    int maxSum=0;

    for (int left = 0; left < numCols; left++)
    {
        int temp[numRows] = {0};

        for (int right = left; right < numCols; right++)
        {
            // Find sum of every mini-row between left and right columns and save it into temp[]
            for (int i = 0; i < numRows; ++i)
                temp[i] += matrix[i][right];

            // Find the maximum sum subarray in temp[].
            int sum = kadane(temp, numRows);

            if (sum > maxSum)
                maxSum = sum;
        }
    }

    return maxSum;
}

 =====>
public static double max2DSubarray(double[][] array, MutableInt returnStartX, MutableInt returnStartY, MutableInt returnEndX, MutableInt returnEndY)
{
int rows = array.length, columns = array[0].length;

double max_so_far = -1, max_ending_here = 0;

for (int row1 = 0; row1 < rows; row1++)
{
double[] tmp = new double[columns];
for (int column = 0; column < columns; column++)
{
tmp[column] = 0;
}

for (int row2 = row1; row2 < rows; row2++)
{
for (int column = 0; column < columns; column++)
{
tmp[column] += array[row2][column];
}
MutableInt tmpStartY = new MutableInt(-1), tmpEndY = new MutableInt(-1);
max_ending_here = max1DSubarray(tmp, tmpStartY, tmpEndY);

if (max_ending_here > max_so_far)
{
returnStartX.setValue(row1);
returnEndX.setValue(row2);
returnStartY.setValue(tmpStartY.intValue());
returnEndY.setValue(tmpEndY.intValue());
max_so_far = max_ending_here;
}
}
}

return max_so_far;
}
  1. find_max_sum(int input[M][N])  
  2. {  
  3.     int tmp[100], n, x1, x2;  
  4.     int cur, max_sum, fx1, fx2, fy1, fy2;  
  5.     int i,j,k;  
  6.     fx1 = fx2 = fy1 = fy2 = max_sum = cur = -1;  
  7.   
  8.     for (i=0; i< M; i++)  
  9.     {  
  10.         for(k=0; k<N; k++)  
  11.             tmp[k] = 0;  
  12.   
  13.         for (j=i; j<M; j++)  
  14.         {  
  15.             for(k=0; k<N; k++)  
  16.                 tmp[k] += input[j][k];  
  17.             kadane(tmp, N, x1, x2, cur);  
  18.   
  19.             if (cur > max_sum)  
  20.             {  
  21.                 fy1 = x1;  
  22.                 fy2 = x2;  
  23.                 fx1 = i;  
  24.                 fx2 = j;  
  25.                 max_sum = cur;  
  26.             }  
  27.         }  
  28.     }  
  29.     cout << "max Sum = " << max_sum << " from (" << fx1 << "," << fy1 << ") to ("  
  30.         << fx2 << "," << fy2 << ")" << endl;  
  31. }  

  1. void kadane(int input[], int n, int &x1, int &x2, int &max)  
  2. {  
  3.     int cur, i;  
  4.     max = 0;  
  5.     cur = 0;  
  6.     x1 = x2 = 0;  
  7.     int lx1, lx2;  
  8.     lx1 = 0;  
  9.     for(int i = 0; i<n; i++)  
  10.     {  
  11.         cur = cur+input[i];  
  12.         if(cur > max)  
  13.         {  
  14.             max = cur;  
  15.             x2 = i;  
  16.             x1 = lx1;  
  17.         }  
  18.         if (cur < 0)  
  19.         {  
  20.             cur = 0;  
  21.             lx1 = i + 1;  
  22.         }  
  23.     }  
  24. }  
http://geekmeal.blogspot.com/2013/02/syntaxhighlighter.html
https://github.com/kevindra/Problems/blob/master/array/MaxSubMatrixSum.cpp
Different solution
The trick is to apply Kadane's algorithm on a 2D matrix. We will consider all the possible 2D matrices which are starting from 0th column and treat them as 1D arrays.
int getMaxSubmatSum2(int a[][COL], int r, int c) {
  int globalmax = 0;
 
  for (int i = 0; i < r; i++)
   for (int j = i; j < r; j++) {
    int localmax = 0;
    for (int k = 0; k < c; k++) {
     localmax = max(localmax + getSubmatSum(i, k, j, k), 0);
     globalmax = max(localmax, globalmax);
    }
   }
 
  return globalmax;
 }
O(N^4)
int getMaxSubmatSum(int a[][COL], int r, int c) {
  int maxsum = 0;
  for (int r1 = 0; r1 < r; r1++) {
   for (int c1 = 0; c1 < c; c1++) {
    for (int r2 = r1; r2 < r; r2++) {
     for (int c2 = c1; c2 < c; c2++) {
      int sum = getSubmatSum(r1, c1, r2, c2);
      maxsum = max(sum, maxsum);
     }
    }
   }
  }
  return maxsum;

 }
Also check
https://plus.google.com/+JefferyYuanLifeLongProgrammer/posts/DScjK4y7iAr
http://comeoncodeon.wordpress.com/2009/04/07/maximum-subarray-in-1-d-and-2-d-array/
Read full article from Find Max sum in a 2D array | PROGRAMMING INTERVIEWS
at
Labels: , , , ,
Subscribe to: Posts (Atom)

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts