Seeking continuous element array and matrix sub-matrix of the largest and the largest and

2010-04-16  来源:本站原创  分类:CPP  人气:201 

1
Given a length n of the one-dimensional array a, please find a sub-array in this array, so this sub-array and the sum = a [i] + a [i +1] + ... ... + a [j] the largest , where i> = 0, i <n,j> = i, j <n,
For example, 31 -41 5926-535897-93 -23 84
59 +26-53 +58 +97 submatrix = 187 was asked for the maximum sub array.
Example code:

#include <iostream>
using namespace std ;

// Direct brute, find out all the possible combinations and    O(N^3)
int getSum1(int a[],int N)
{
    int max=-10000000;
    for(int i=0;i<N;i++)
    {
        for(int j=i;j<N;j++)
        {
            int tmp=0;
            for(int k=i;k<=j;k++)
                tmp+=a[k];
            if(tmp>max)
                max=tmp;
        }
    }
    return max;
}

// With memory of recursive method   O(N^2)
int getSum2(int a[],int N)
{
    int* cumarr=new int[N];
    cumarr[0]=a[0];
    // Pretreatment, makes the combinatorial and easier
    for(int i=0;i<N;i++)// Some parts and to build first
    {
        cumarr[i]=cumarr[i-1]+a[i];
    }
    int max=-10000000;

    for(int i=0;i<N;i++)
    {
        for(int j=i;j<N;j++)
        {
            // Optimization of place
            int tmp=cumarr[j]=cumarr[i];
            if(tmp>max)
                max=tmp;
        }
    }
    delete[] cumarr;
    return max;
}

// The third kind  ,
int maxSubArray(int a[],int N)
{
    int b=0,max=-10000000;
    for(int i=0;i<N;i++)
    {
        if(b>0) b+=a[i]; // Greater than 0, the previous accumulated
        else b=a[i];
        if(b>max) max=b;
    }
    return max;
}

int main ()
{
    int a[]={31,-41,59,26,-53,58,97,-93,-23, 84};
    int N=sizeof(a)/sizeof(a[0]);
    cout<<getSum1(a,N)<<endl;
    cout<<getSum1(a,N)<<endl;
    cout<<maxSubArray(a,N)<<endl;
        return 0 ;
}

2

相关文章
  • Seeking continuous element array and matrix sub-matrix of the largest and the largest and 2010-04-16

    1 Given a length n of the one-dimensional array a, please find a sub-array in this array, so this sub-array and the sum = a [i] + a [i +1] + ... ... + a [j] the largest , where i> = 0, i <n,j> = i, j <n, For example, 31 -41 5926-535897-93 -23

  • javascript remove element Array built-in objects 2011-05-30

    In the javascript in, Array object does not provide delete method to delete the array, and some people will say there is a js in their own way to delete an array element delete, delete but you did not change after the length of the array, this is not

  • Understand the matrix (2) 2010-06-19

    Then understand matrix. Li said on a "matrix is a description of movement", to now, not what everyone seems to view. But I believe that sooner or later there will be Department of Mathematics, the netizens all decided to switch origin. Because t

  • Have the right of the adjacency matrix of the storage structure 2010-05-07

    Figure: Figure is a vertex set V and the relationship between vertex set E (the set of edges) consisting of a data structure can be defined as the dual group G = (V, E). Directed graph: If the arrow indicating the side is directional, such a graph is

  • POJ 1977 Odd Loving Bakers [matrix of fast power, good a model transformation problem] 2010-05-30

    Odd Loving Bakers Time Limit: 2000MS Memory Limit: 30000K Total Submissions: 1372 Accepted: 429 Description There is a group of N bakers in the town of Utopia. These bakers hold a monthly celebration in which they award a prize to some of the luckier

  • Sparse matrix transpose 2010-06-29

    #include<iostream> #define MAX 1000 using namespace std; typedef struct Elem{ int row,col,value; }Elem; typedef struct Matrix{ Elem elems[MAX+1]; int m,n,len; }Matrix; int position[MAX];// Each line begins with the position of an element int num[MAX

  • Clockwise from outside to inside print digital matrix 2010-07-13

    # Print to the standard output of digital matrix . # Clockwise, from outside to inside printing matrix . The starting point is the upper-left corner of the matrix . class Matrix def initialize(width) @n = 0 @width = width # The width of the matrix #

  • Reading new.delete. Point to a continuous space pointer. Array. Space release. Space applications [C + +] [Memory Management] Impression 2010-08-13

    1. Use new and delete operator, the rate of change when the PF Ctrl + Alt + Del to enter the Task Manager, performance, run the following code, and observe the PF rate changes. Known, new operator to increase PF rate, delete to restore the PF rate. N

  • as3 explained in the matrix, finally found 2010-09-10

    Transfer from: http://blog.sina.com.cn/s/blog_629045ef0100f7ld.html Perhaps the title to see so many poor or middle school math classes nap friends will feel resentment, but rest assured that here in the Matrix has been simplified so many trivial ste

  • Algorithms: saddle point matrix 2010-10-12

    10.12 find the saddle point of a matrix, that is the line's smallest and largest points in the column. The idea is: 1. To find the smallest i-line number 2. Testing whether the number of the largest number of the column def saddle_point(arr) # arr M-

  • Android drawing of the Matrix (b) 2010-10-23

    Android on a drawing of the Matrix (a) Matrix spoke about the principles and calculation methods, related to higher mathematics, a bit difficult to understand. Fortunately Android Matrix which provides a series of operations Out convenient interface.

  • Detailed in the Matrix as3 2010-12-10

    See the title may be very large or high school math class nap bad friends will feel resentment, but rest assured that here in the Matrix has simplified the steps so many trivial, do not you take a piece of paper hard to do calculations. Friends of th

  • Zig-zag print matrix 2011-05-25

    Enter a number i, and then build i × i matrix, the matrix content increases along the 45 degree line Such as type 4, the matrix 0156 24712 381,113 9101415 Java Source code is as follows : import java.io.*; public class Zigzag { public static void mai

  • Understand the matrix (3) 2010-06-19

    The articles published in the last year in April. In the second part of the end, I said: "Matrix not only described as a linear transformation, but also as a basis of description. And as a matrix transformation, not only to a point in the linear spac

  • Baidu document Question: Find k in the matrix 2010-07-05

    Title: Given the following numbers n * n matrix, each row is strictly increasing from left to right, each column of data is strictly increasing 1 2 3 356 489 Now to design an algorithm that, given a number k k determine whether this matrix. Describe

  • Matrix scaling picture, rotate pictures 2010-09-26

    android.graphics.Matrix Zoom picture file : int bmpWidth = bitmap.getWidth(); int bmpHeight = bitmap.getHeight(); // To reduce the proportion of 0.8 float scale = 0.8; // 1.2 scaleWidth = scaleWidth * scale; // scaleWidth The initial value 1.0f scale

  • Graphics ----- Matrix ScaleToFit 2010-10-12

    1. Matrix.ScaleToFit new Matrix.ScaleToFit[] { Matrix.ScaleToFit.FILL, Matrix.ScaleToFit.START, Matrix.ScaleToFit.CENTER, Matrix.ScaleToFit.END }; private void drawFit(Canvas canvas, int index, Matrix.ScaleToFit stf) { canvas.save(); setSrcR(index);

  • Basic use Matrix (a) 2010-10-20

    Rotation java.lang.Object ↳ android.graphics.Matrix Public Constructors Matrix () Create an identity matrix Matrix ( Matrix src) Create a matrix that is a (deep) copy of src void setRotate (float degrees) Set the matrix to rotate about (0,0) by the s

  • ImageView in the dynamic image zoom (using Matrix object to scale the image file) 2010-11-13

    AndroidDecodeFile file package com.wm.AndroidDecodeFile; import java.io.File; import android.app.Activity; import android.graphics.Bitmap; import android.graphics.BitmapFactory; import android.graphics.Matrix; import android.os.Bundle; import android

  • Solve the sparse matrix by adding the list 2010-12-01

    author: 081201108 weiguisheng Title: find two matrices and (summation of these two matrices also exist) f1.txt 4 4 001 112 223 334 f2.txt 45 001 022 115 224 338 code is as follows: # Include <iostream> using namespace std; typedef struct node * link